Programozás‎ > ‎Feladatok‎ > ‎

Alkatrészgyártás

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