Alkatrészeket gyártó üzem N megrendelést kapott. Minden megrendelésre tudja, hogy mennyi idő
szükséges az alkatrész legyártásához. Az üzemnek van legalább N munkagépe, így minden alkatrészt
külön gépen tud legyártani. A gyártás előtt minden alkatrészt elő kell készíteni, de ezt az elő-
készítést csak egy gép tudja végezni. Az is ismert, hogy az egyes alkatrészek előkészítése mennyi
időt igényel. Minden alkatrész előkészítése után azonnal elkezdődik a gyártása.
Feladat
Készíts programot, amely megadja, hogy milyen sorrendben kell előkészíteni az alkatrészeket,
hogy az összes legyártása a leghamarabb befejeződjön!
Bemenet
A standard bemenet első sora az alkatrészek számát tartalmazza (1≤N≤30 000). A második és a harmadik sor pontosan N egész számot tartalmaz egy-egy szóközzel elválasztva. A második sor i-edik eleme az i-edik alkatrész előkészítési ideje, a harmadik sor i-edik eleme pedig az
alkatrész legyártásához szükséges idő. A második és harmadik sorban minden szám értéke legfeljebb
1000.
Kimenet
A standard kimenet első sorába az összes alkatrész legyártásához szükséges minimális időt
kell írni! A második sor az alkatrészek sorszámainak egy olyan felsorolását tartalmazza (egy-egy
szóközzel elválasztva) amely a legkorábbi befejezést biztosítja! Több megoldás esetén bármelyik
megadható.
Példa
Bemenet |
Kimenet |
3 1 3 3 4 1 5 | 8 3 1 2
|
Tesztadatok
További tesztadatok a mester.inf.elte.hu oldalon.
Címkék
A feladat forrása: mester.inf.elte.hu, Haladó > Mohó algoritmusok > Alkatrészgyártás
Algoritmusok: mohó algoritmus
megoldás |