Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | kcover.in, kcover.out | Sursă | Happy Coding 2008 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kcover
Se dau N puncte pe axa OX. Punctele sunt numerotate de la 1 la N, iar punctul i este pozitionat la coordonata xi. Se cere amplasarea pe axa OX a K intervale inchise, astfel incat fiecare din cele N puncte sa fie acoperit de cel putin unul din cele K intervale (un punct i este acoperit de un interval [a,b], daca a≤xi≤b). Se doreste ca suma lungimilor celor K intervale sa fie minima.
Date de intrare
Pe prima linie a fisierului de intrare kcover.in se afla numarul intreg T, reprezentand numarul de teste descrise in continuare. Fiecare test este reprezentat sub forma a 2 linii. Pe prima linie se afla numerele intregi N si K, separate printr-un spatiu. Pe a doua linie se afla coordonatele celor N puncte, separate prin spatii.
Date de iesire
Pentru fiecare din cele T teste din fisierul de intrare, in ordinea in care sunt date in fisier, veti afisa in fisierul de iesire kcover.out cate o linie reprezentand suma minima a lungimilor celor K intervale, astfel incat fiecare punct sa fie acoperit.
Restrictii
- 1 ≤ T ≤ 10
- 1 ≤ K ≤ N ≤ 100.000
- -2.000.000.000 ≤ xi ≤ 2.000.000.000
- Lungimea unui interval inchis [a,b] este egala cu b-a.
Exemplu
| kcover.in | kcover.out |
|---|---|
| 6 6 1 2 4 1 8 3 6 6 2 2 4 1 8 3 6 6 3 2 4 1 8 3 6 6 4 2 4 1 8 3 6 6 5 2 4 1 8 3 6 6 6 2 4 1 8 3 6 | 7 5 3 2 1 0 |
