NézetNyomtat

Bíróság (Megoldás)
Versenyek > IOI/CEOI felkészítő > 2005
Címkék > Feladat
Elmélet > Algoritmusok > Mohó
Elmélet > Algoritmusok > Rendezések

Bíróság

Van egy bíróság, ahol ügyeket tárgyalnak. Minden ügy tárgyalása egy napot vesz igénybe. Minden nap pontosan egy ügyet tárgyalnak. Így N (1<=N<=10000) üggyel N nap alatt végeznek. Minden ügynek két jellemzője van: egy H határideje (1<=H<=N), ameddig az ügyet le kell tárgyalni és egy B büntetése (1<=B<=1000), amelyet ki kell fizetni, ha az ügy nincs letárgyalva a határidő napjáig. (a határidő napon tárgyalt ügyért nem kell büntetést fizetni).
Feladat egy olyan program írása, amely adott ügyekre meghatározza a legkisebb összbüntetést és megadja, hogy milyen sorrendben kell letárgyalni az ügyeket ehhez a minimumhoz.

Bemenet

A bemenő file (biroX.be) első sora tartalmazza N értékért, a többi N sor két számot tartalmaz: az i+1edik sor tartalmazza az i-edik ügy határidejét, illetve büntetését.

Kimenet

A kimenő file (biroX.ki) első sorában a minimális összbüntetésnek kell szerepelnie. A további N sor egy-egy számot tartalmaz, az i+1-edik sor tartalmazza az i-edik napon tárgyalt ügy sorszámát.

Példa be- és kimenet:

Biro0.be Biro0.ki
10 9 10 10 5 1 10 3 1 2 6 6 10 7 4 3 8 7 2 2 2 3 3 5 8 4 9 6 7 10 1 2

Tesztadatok