Minimum uzastopnih

View as PDF

Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 64M

Problem type

Dat je niz A koji se sastoji od N celih brojeva i niz B koji je na početku prazan. Želimo da iz niza A prebacimo tačno T elemenata u niz B tako što ćemo T puta ponoviti sledeću stvar:

  • Izabrati nekih K uzastopnih elemenata niza A, a zatim najmanji od njih izbaciti iz niza A i ubaciti u niz B. Ukoliko ima više istih najmanjih elemenata među izabranih K uzastopnih, može se izbaciti bilo koji.

Ovo želimo da uradimo na takav način da nakon izvršenih svih T prebacivanja, razlika maksimalnog i minimalnog elementa u nizu B bude najmanja moguća. Ispisati ovu najmanju razliku koju možemo da dobijemo ukoliko optimalno biramo operacije.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se tri broja odvojena razmakom N, K i T. U drugoj liniji standardnog ulaza nalazi se N brojeva odvojenih razmakom, koji predstavljaju niz A.

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza ispisati najmanju razliku između maksimalnog i minimalnog elementa u nizu B koju možemo da dobijemo optimalnim izborom operacija.

Primer
Standardni ulaz          Standardni izlaz
5 3 2
10 8 7 12 1
1
5 3 3
10 8 7 12 1
7
Objašnjenje test primera

U prvom test primeru u prvoj operaciji možemo izabrati podniz (A_2, A_3, A_4) = (8, 7, 12) od kojih je najmanji broj 7 i njega ćemo izbaciti iz niza A i prebaciti u niz B, nakon ovoga niz A postaje A = (10, 8, 12, 1). U drugoj operaciji sada moramo izabrati podniz (A_1, A_2, A_3) = (10, 8, 12) od kojih je najmanji broj 8 kog prebacujemo u niz B. Niz B je sada B = (7, 8) i razlika najvećeg i najmanjeg broja je 1.

U drugom test primeru možemo ponoviti iste operacije kao u prvom, u trećoj operaciji će nam samo ostati još da prebacimo minimum od (10, 12, 1) u niz B, što je broj 1, pa će nam niz B biti B = (7, 8, 1) gde je razlika izmeđeu najvećeg i najmanjeg broja 7.

Ograničenja i podzadaci

(1 \le N \le 10^5)
(1 \le K \le N)
(1 \le T \le N - K + 1)
(1 \le A_i \le 10^9)

Test primeri su podeljeni u 4 disjunktne grupe:
U test primerima vrednim 15 poena: (K = 1).
U test primerima vrednim 30 poena: (1 \le A_i \le 100).
U test primerima vrednim 30 poena: (1 \le N \le 2000).
U test primerima vrednim 25 poena: Nema dodatnih ograničenja.


Comments

There are no comments at the moment.