Adott N pozitív egész szám. Keresünk legfeljebb K olyan zárt intervallumot, hogy minden megadott szám benne van valamelyik intervallumban és az intervallumok összhossza a lehető legkisebb. Minden lefedő [a,b] intervallumra teljesülni kell, hogy a<b. Az intervallum hossza a b-a érték.
Feladat
Készíts programot, amely megadja a legkisebb összhosszú lefedő intervallumokat!
Bemenet
Az lefed.be szöveges állomány első sorában két egész szám van, a lefedendő számok N száma (1≤N≤100 000) és a lefedésre használható intervallumok számának K maximuma (1≤K≤N). A második sor pontosan N pozitív egész számot tartalmaz (egy-egy szóközzel elválasztva), a lefedendő számokat. A számok nem nagyobbak, mint 2 000 000.
Kimenet
Az lefed.ki szöveges állomány első sorába a lefedő intervallumok összhosszát kell írni. A további legfeljebb K sorba kell kiírni a lefedő intervallumokat, egy sorba egy intervallum kezdő és végpontját. Az intervallumokat kezdőpontjuk szerint növekvő sorrendben kell kiírni. Több megoldás esetén bármelyik megadható.
Példa
Bemenet |
Kimenet |
7 3 3 1 4 11 7 9 15 | 8 1 4 7 11 15 16
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2013, 11-13. évfolyam, döntő
Algoritmusok:
megoldás |