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 | 
2004-2016 BDG algoritmus szakkör