Programozás‎ > ‎Feladatok‎ > ‎

Lefedés

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