Z góry uprzedzam, że przedstawiony tutaj sposób nie przejdzie na Athinie, gdyż Pan Duraj z pewnością odbije takie zadanie ręcznie, użyjemy w nim bowiem sposoby "sprytnego" - żeby się za dużo nie naklepać.
Celem tego tematu jest pokazanie szybkiego sposoby na tego typu problemu osobom, które go jeszcze nie znają.
Co w tym zadaniu jest uciążliwego?? No, przynajmniej według mnie pisanie kopca, ale można tego uniknąć!! Bo w STLu jest już kopiec :)
Tylko jak go dodać do naszego programu?? Potrzebujemy na początku linijkę:
#include <queue>
a potem jak już mamy strukturę, nazwijmy ją "partia", to robimy coś takiego:
priority_queue <partia> kopiec;
żeby to działało, musimy jakoś naszemu programowi dać do zrozumienia jak ma na tym kopcu naszym ustawiać te partie, a żeby to zrobić, potrzebujemy funkcji, która będzie działała jak znak "<" dla naszych partii, a ona będzie wyglądać bodajże jakoś tak:
bool operator<(partia a, partia b)
{
return (a.glosy/(a.mandaty+1)<b.glosy/(b.mandaty+1) || a.glosy/(a.mandaty+1)==b.glosy/(b.mandaty+1) && a.nr>b.nr);
}
I teraz już nie musimy się o nic więcej martwić, bo kopiec zrobi się sam :) A jak teraz tego używać??
To, co zwykle na kopcu było jako tab[1], czyli to na szczycie kopca, to teraz:
kopiec.top();
żeby coś dodać do kopca, używamy:
kopiec.push(to_co_wrzucamy)
żeby coś z niego wyrzucić używamy:
kopiec.pop() - działanie takie samo jak lekcyjne "ExtractMax()"
Jak chcemy dodać partii mandat, to robimy to tak:
kopiec.top().mandaty++;
albo
mandaty[kopiec.top().nr]++;
No i cały czas o wszystko jest zadbane, nie musimy pisać HeapDowna, ani innych funkcji, bo mamy je już gotowe :)
[Lech Duraj] Przyznam się, że tak właśnie pisałem wzorcówkę ;-) Zależało mi na czasie i na tym, żeby nie zrobić błędu. Są jednak sytuacje, kiedy trzeba mimo wszystko klepnąć cały kopiec.
