Szympans je banany. Zjedzenie jednego owocu zajmuje mu minutę (je po jednym na raz).
Wiadomo, że każdy z bananów psuje się po pewnym czasie, a szympans chce spożyć jak najwięcej
świeżych bananów – zepsutych nie rusza. Zaproponuj możliwie efektywny algorytm, który mając
zadane n bananów (1<=n<=1000000), z których i-ty owoc psuje się po bi minutach (1<=bi<=1000),
wyznaczy optymalną kolejność jedzenia świeżych bananów, przy której szympans najbardziej się
naje. W przypadku istnienia kilku optymalnych kolejności, algorytm może podać dowolne z nich.
Dla przykładowych danych:
1, 5, 4, 1, 3 //czasy ważności (w minutach) pięciu bananów (numeracja od 1 do 5)
Wynikiem są cztery kolejno jedzone banany o numerach:
1 3 5 2 //nie jest możliwe, by szympans zjadł wszystkie 5 bananów
Wiem, że algorytm za każdym razem ma wybierać banan, którego data ważności jest najkrótsza. Tylko złożoność mi wychodzi pseudowielomianowa.
Pseudokod:
int banany[]={1,5,4,1,3};
while(min!=0){
for(i=0;i<banany.length;i++){
if(banany[i]<min){
min=banany[i]; //znalezienie banana z najkrótszą ważnością
index=i; zapamiętanie indeksu banana
}
banany[i]--; // upływa czas gdy szympans je banana przez 1 minutę
}
banany[index]=0; // wykasowanie banana zjedzonego przez "zrobienie" go zepsutym
dodaj_do_wyniku (index);
}
co o tym sądzicie?
Proszę o wyrozumiałość, jeśli głupotę napisałem