Íme ismét egy válogatópélda, méghozzá 2006-ból. Akkor és abban a mezőnyben olyan nehéznek számított, hogy senki nem oldotta meg, pedig két teljesen különböző megoldása is van. Remélem, ez már a múlt, és ti mind a két módon meg tudjátok oldani. (És ezt komolyan mondom, mind a kettő megoldás fontos, úgyhogy akkor is érdemes továbbgondolkozni rajta, ha egyféleképp már megy.)

Feladat

Adott N konténer egy sorban, és rendelkezésünkre áll K kamion, amikkel el kell őket szállítanunk. Az első néhány konténert rakhatjuk az első kamionra, a következő néhányat a másodikra, és így tovább, azaz minden kamion a konténerek egy részintervallumát szállítja. Ismerjük a konténerek súlyát is. Egy kamionra akármennyi (de legalább egy), és akármilyen nehéz konténereket rakhatunk, de a cél az, hogy a súlyt minél egyenletesebben osszuk el a kamionok között. Egész pontosan az egy kamionra jutó maximális összsúlyt akarjuk minimalizálni.

input

Az első sorban két egész szám, a konténerek (1<=N<=5000) és a kamionok (2<=K<=N) száma található. A második sor N egész számból áll, közülük az i-edik az i-edik konténer súlyát jelöli. Feltehető, hogy a konténerek összsúlya belefér egy négybájtos integerbe.

output

Az első sor egy egész számot tartalmazzon, az optimális elosztásban maximálisan terhelt kamion terhelését. A második sorba K egész számot kell kiírni, indexek egy monoton növő sorozatát adják: a j-edik szám annak a konténernek a sorszáma legyen, ahonnan kezdve a j-edik kamionra pakoljuk őket.

Olimpiai válogatóverseny, 2006/13

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.