Masala C
Hasan va Maxsus O'chirish
Quyidagi massiv berilgan: \(a\) uzunligi \(n\) bo'lgan butun sonlardan iborat. Keling, massivning \(f(a)\) funksiyasini aniqlaymiz, u massivdagi turli xil (unikal) butun sonlar soniga teng bo'ladi \(a\).
Masalan, \(f([1, 2, 4, 4, 2]) = 3\) , chunki unda uchta turli xil son mavjud: \(\{1,2,4\}\).
Siz faqat bitta amalni bajarishga ruxsat berilgansiz: uzunligi \(k\) bo'lgan istalgan qism massivni tanlab, uni olib tashlash.
Masalan, agar \(a =[1, 2, 4, 4, 2]\) va \(k = 2\), bo'lsa, agar 3-chi va 4-chi elementlarni olib tashlasak, hosil bo'lgan massiv\([1, 2, 2]\) bo'ladi va\(f(a)=2\)
Operatsiyani bajargandan so‘ng, \(\min(f(a))\) .
Birinchi qatorda bitta butun son berilgan:
\(t (1 ≤ t ≤ 10^4 )\) – test holatlarining soni.
Har bir test holatining birinchi qatori ikkita butun sondan iborat:
\(n\) va \(k\) (\(1 ≤ k < n ≤ 2·10^5 \)) – mos ravishda massiv uzunligi va olib tashlanadigan qism massiv uzunligi.
Har bir test holatining ikkinchi qatori
\(n\) ta butun sonni o‘z ichiga oladi:
\(a_1,a_2,..,a_n\) (\(1 ≤ a_i ≤ 10^{11} \)).
Shuningdek, \(n\) ning yig‘indisi \(4 · 10^5\) dan oshmasligi kafolatlangan.
Har bir test holati uchun bitta butun sonni chiqarish kerak:
\(\min(f(a))\).
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 3 2 1 2 3 5 2 1 2 4 4 2 6 1 1 1 4 5 1 4 10 3 2 1 4 7 4 8 3 6 4 7 |
1 2 2 4 |
Birinchi test holati uchun:
Qaysi qism massivni tanlamang, natija har doim \(1\) ga teng bo'ladi.
Ikkinchi test holati uchun:
Qism massivni tanlashning ikki usuli mavjud: \([1,2]\) yoki \([4,4]\),
va hosil bo'lgan massiv ikkala holatda ham \(2\) ta turli xil sonlarga ega bo'ladi.
To‘rtinchi test holati uchun:
Siz \([8,3,6]\) ni tanlashingiz kerak va hosil bo'lgan massiv
\([2,1,4,7,6,4,7]\) bo‘ladi, bu holda qiymat \(4\) ga teng bo‘ladi.
Telegram kanalimizga obuna bo'ling