[Algorytmy] OIG VI - Apteka

[Mike148]

Rozwiązuje właśnie zadanie z ostatniego OIG pt. Apteka ( ... t&con=OIG6)
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.

Kod: Zaznacz cały

#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
", suma );
    
    return 0;
}

Jakieś propozycje ?

[Rjiuk]

Za każdym razem kiedy szukasz minimum , musisz przeszukać całą tablice. Zauważ że pesymistycznie będziesz przesuwał się co jeden , w sensie , LastMin będzie rósł o jeden. Co daje już jakiś kwadrat , nic miłego.

A więc najlepsze co można zrobić to stablicować sobie minima na przedziale. Zauważ że interesują Cię tylko przedziały od (N-2 ... LastMin) . Zrób sobie minima prefiksowe . Taki preprocesing, który dla każdej pozycji <=N-2 pozwoli Ci w czasie stałym odpowiedź na zapytanie jakie jest minimum i gdzie się znajduje

Jeżeli sobie nie dasz rady wal na forum , ale teraz powinno już pójść gładko.

PS: zapamiętuj minima dla każdej pozycji i powodzenia w dalszej nauce

Pozdrawiam

[Mike148]

Hej!
Dzięki za pomoc. Sorki, że dopiero teraz, ale chory byłem i nie miałem siły myśleć . Hmm... Rozumiem o co ci chodzi tylko nie wiem za bardzo jak to zapisać. Próbowałem to zrobić jakimś sortem i przy tym zamieniać pozycję, ale ten sposób nie działa.

[Rjiuk]

Pokaże Ci idee:
załóżmy że mamy sobie takie liczby :

Kod: Zaznacz cały

6 3 3 5 2 7 1 4

teraz chcemy mieć od lewej minimum dla całego przedziału bo tylko taki Cię interesuje :

Kod: Zaznacz cały

6 3 3 3 2 2 1 1

w jaki sposób to zrobić ?

Kod: Zaznacz cały

minima(0)= INF  jakas duza liczba
for(i,1,N)
 minima(i)=min(minia(i-1),tab(i) )

Coś takiego