Mike148 Temat założony przez niniejszego użytkownika |
OIG VI - Apteka » 2012-12-26 15:55:04 Po raz kolejny powracam z algorytmem z OIG i będę was nudził :D Całą sprawa się ma tak - algorytm jest, działa dobrze zdobywa 88 ptk, a przy reszcie jest wywłaszczany. Pomysł dobry tylko optymalizacja. Cały problem leży w wyszukiwaniu najmniejszej wartości w tablicy. #include <cstdio>
#define MAX_N 1000000
int main()
{
int n, i;
scanf( "%d", & n );
int min = 0, minPos = 0, lastMin = 0, lMin = - 1;
unsigned long long suma = 0;
static unsigned int k[ MAX_N ];
for( i = 0; i < n; i++ )
{
scanf( "%d", & k[ i ] );
}
min = k[ n - 1 ];
minPos = n - 1;
lastMin = - 1;
while( lastMin !=( n - 1 ) )
{
for( i = n - 1; i > lastMin; i-- )
{
if( min >= k[ i ] )
{
min = k[ i ];
minPos = i;
}
}
suma += k[ minPos ] *( minPos - lMin );
lMin = lastMin = minPos;
min = k[ n - 1 ];
}
printf( "%lld\n", suma );
return 0;
}
Jakieś propozycje ? |
|
Mrovqa |
» 2012-12-26 20:26:58 Tak, linka do zadania byś dał, jeśli oczekujesz pomocy. |
|
withelm |
» 2012-12-26 21:47:05 |
|
Mike148 Temat założony przez niniejszego użytkownika |
» 2012-12-27 00:04:18
http://main.edu.pl/pl/user.phtml?op=showtask&task=apt&con=OIG6
ehh, skoro masz TLE jak idziesz od początku tablicy to czy nie warto było by iść od końca?
|
A czy sprawdzałeś pętlę for. Przecież ona zawsze idzie od końca w obu przypadkach ?! |
|
withelm |
» 2012-12-27 01:47:30 hmm, to znaczy ze głupio robisz to od konca :P
załóżmy sobie ze masz jakies minimum z tablicy [i..n] o jego index
teraz jestes patrzysz na element i-1 i jesli jest wiekszy to nic z nim nie robisz, a co jeśli t[i-1] jest mniejszy od naszego aktualnego minimum? |
|
Mike148 Temat założony przez niniejszego użytkownika |
» 2012-12-27 14:44:36 @withelm Chyba się do końca niezbyt rozumiemy. Przecież moja pętla działa tak jak piszesz. Poprawiłem trochę kod. Przechodzi jeden test więcej. Zostaje wywłaszczony na dwóch testach (11b, 17b) #include <cstdio>
#define MAX_N 1000000
int main()
{
int n, i;
scanf( "%d", & n );
int min = 0, minPos = 0, lastMin = 0;
unsigned long long suma = 0;
static unsigned int k[ MAX_N ];
for( i = 0; i < n; i++ )
{
scanf( "%d", & k[ i ] );
}
min = k[ n - 1 ];
minPos = n - 1;
lastMin = - 1;
while( lastMin !=( n - 1 ) )
{
for( i = n - 2; i > lastMin; i-- )
{
if( k[ i ] < min )
{
min = k[ i ];
minPos = i;
}
}
suma += k[ minPos ] *( minPos - lastMin );
lastMin = minPos;
min = k[ n - 1 ];
minPos = n - 1;
}
printf( "%lld\n", suma );
return 0;
}
|
|
withelm |
» 2012-12-27 16:26:21 Własnie nie.
Zobacz, Ty znajdujesz te minimum i jest fajnie. Ale gdy kolejny raz szukasz nowego minimum to przechodzisz znowu od konca tablicy i tak w kółko macieju. Sciągnij sobie testy i policz ile razy Twój kod wykonuje obrotów pętli.
Btw, kto Cię nauczył używac #define do ustalania stałych i po co takie udziwnienia "unsigned long long suma" i "static unsigned int k[ MAX_N ]" kiedys to Cię tak w <<...>> kopnie że nie bedziesz wiedział jak się nazywasz. Aha i używaj tabulatorów a nie spacji.
|
|
Mike148 Temat założony przez niniejszego użytkownika |
» 2012-12-27 16:58:37 Gdy szukam ponownie minimum to przechodzę od końca ponieważ jak widzisz zapisuje pozycję tego minimum wa tablicy do "minPos" i chcę tam mieć ostatnie wystąpienie w tablicy(najbliższe końca) a przeszukuję tablicę do ostatniej pozycji minimum "lastMin = minPos". Co do btw. #define MAX_N 1000000 Przy algorytmice czasami takie coś się pojawia. Po za tym co ci to przeszkadza. Stała i tak jest zamieniana przez preprocesor przy kompilacji więc nic to algorytmu nie obciąża, a jest czytelniej i bardziej widocznie. Jak się popatrzyłeś to od razu zobaczyłeś ile może być maksymalnie n; unsigned long long Skrajne przypadki : n = 10^9 każde Ci = 10^6 n * Ci = 10^9 * 10^6 = 10^15 Pojęcie zmiennej i podstawowe typy danychZnaku i tak nie potrzebujemy stąd unsigned, a i tak ci to oszczędzi bajtów static unsigned int k[ MAX_N ] Uboczny efekt - zerowanie tablicy. Tutaj nie jest potrzebne aż tak, ale zawsze lepiej. | kiedys to Cię tak w dupę kopnie że nie bedziesz wiedział jak się nazywasz. Aha i używaj tabulatorów a nie spacji. |
Czemu ma mnie kopnąć w <<...>> ? oraz O co ci chodzi z tabulatorami zamiast spacji (gdzie ?) :D |
|
| « 1 » 2 |