Pisałem dzisiaj drugi etap OIJ-a, i mam delikatne wątpliowści czy mój kod jest dobry. Przekopiuję treść ręcznie, bo nie jest jeszcze dostępna na sio2.
Treść:
Bajtek wraz z kolegami pisze swoją pierwszą grę komputerową. Gra jest osadzona w środowisku fantasy i polega na
uratowaniu księżniczki. Żeby ją uratować, gracz musi przechodzić labirynty oraz pokonywać potwory.
Gra składa się z plansz, które trzeba przechodzić po kolei. Każda polega na przejściu labiryntu, na końcu którego
znajduje się skrzynia skarbów, bądź potwór. Jeśli na końcu planszy znajduje się skrzynia skarbów, gracz ją otwiera i zdobywa
pewną liczbę diamentów. Jeśli plansza kończy się potworem, gracz musi go pokonać, żeby ukończyć planszę. Każdy potwór
jest bardzo wytrzymały i żeby go pokonać gracz potrzebuje specjalnego miecza, którego może kupić u handlarza, który
znajduje się pod koniec każdej planszy. Żeby kupić miecz, gracz musi zapłacić określoną liczbę diamentów. Każdy potwór
jest jest wrażliwy na inny miecz, gracz nie zdobywa diamentów w inny sposób niż przez otwieranie skrzyń oraz nie wydaje
ich w inny sposób niż na zakup mieczy. Gracz zaczyna grę z zerową liczbą diamentów.
Gra wyróżnia się spośród innych mechaniką zamiany. Gracz może zamienić każdego potwora w skrzynię skarbów, w
której będzie tyle diamentów, ile kosztuje miecz niezbędny do pokonania tego potwora. Gracz może użyć tej możliwości na
każdej planszy, która kończy się potworem.
Bajtek zaprojektował już plansze, teraz pracuje nad osiągnięciami. Jedno z planowanych osiągnięć polega na przejściu
gry używając najmniejszej liczby zamian. Niestety, Bajtek nie wie, jaka to liczba. Pomóż mu i napisz program, którego
będzie mógł użyć, żeby dowiedzieć się, ile najmniej zamian potrzeba do ukończenia gry.
Wejście:
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna (1 ≤ ≤ 500 000) określająca liczbę plansz w grze
Bajtka. W drugim (ostatnim) wierszu wejścia znajduje się ciąg liczb całkowitych (−109 ≤ ≤ 109
) pooddzielanych
pojedynczymi odstępami opisujące jak kończą się kolejne plansze. Jeśli liczba
jest nieujemna, to na końcu -tej planszy
znajduje się skrzynia skarbów, która zawiera diamentów. Jeśli
jest ujemne, na końcu planszy znajduje się potwór,
którego można pokonać tylko mieczem, który kosztuje − diamentów
Wyjście:
Twój program powinien wypisać na wyjście dokładnie jedną nieujemną liczbę całkowitą – minimalną liczbę zamian
niezbędną do ukończenia gry.
No i pomysł miałem taki, żeby na multisecie trzymać ujemne, te które mogę zjeść i jak jak A[i] >= 0, to bilans += A[i], a jak bilans jest < 0, to jem od największych dopóki bilans jest < 0. O(N lg N).
kod:
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
int n = 0, wczytana_liczba = 0, wyn = 0;
ll masa = 0;
vector<int> liczby;
multiset<int> do_zjedzenia;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> wczytana_liczba;
liczby.push_back(wczytana_liczba);
}
for (int i = 0; i < n; ++i)
{
if (liczby[i] >= 0)
masa += (ll)liczby[i];
else
{
ll val = abs((ll)liczby[i]);
masa -= val;
do_zjedzenia.insert((ll)2 * val);
while (masa < 0)
{
wyn++;
masa += *do_zjedzenia.rbegin();
do_zjedzenia.erase(do_zjedzenia.lower_bound(*do_zjedzenia.rbegin()));
}
}
}
cout << wyn << '\n';
return 0;
}
Widzi ktoś jakiś błąd w pomyśle / kodzie?
Z góry dziekuję za pomoc i poświęcony czas!
