Masala G
Quvnoq Prefixlar
Nusrat yoshligida raqamlar bilan o'ynashni yaxshi ko'rardi. U har doim raqamlarni almashtirib o'ynaydi. Lekin bu safar bu o'yiniga biroz o'zgartirish kiritmoqchi. Uni N ta raqami bor uni A massivni ichiga joylashtirib chiqqan. Va uni ichidagi ba'zi elementlarni o'zgartirib chiqmoqchi bo'ldi. Lekin bu hammasi ham emas u massivni prefixlari eng maksimal bo'lgan manfiy joyni iloji boricha kichiklashtirmoqchi (Yaxshiroq tushunish uchun izohga qarang) va bu sonni q bilan belgilaydi. Siz massivni istalgancha o'zgartirishingiz mumkin. Lekin bitta sharti bor va shart quyidagicha: Sizga p massiv beriladi va bu massiv 1 va 0 lardan iborat bu massivning uzunligi N asl massivning uzunligi bilan teng agar l[i]=1 bo'ladigan bo'lsa siz A[i] sini joyini o'zgartirolmaysiz, agar l[i]=0 bo'lsa va boshqa l[j]=0 bo'lsa siz A[i] ni va A[j] sini o'rnini almashtirishingiz mumkin va bu ishni istaganingizcha takrorlashingiz mumkin. Tasavvur qiling sizda pref nomli massiv bor va bunda A massivning barcha prefix yig'indilari yozib chiqilgan. misol uchun A = [1, 2, 3, 4, 5] bo'ladigan bo'lsa pref = [1, 3, 6, 10, 15] bo'ladi.
Bu yerda esa q quyidagicha aniqlanadi:
A massivining prefix yig'indilari orasida manfiy bo'lib qoladigan eng oxirgi indeks q deb belgilanadi. Agar prefixlarning ichida umuman manfiy qiymat bo'lmasa, unda q = 0 deb olinadi. Masalan, agar A = [2, -5, 1, 3] bo'lsa, pref = [2, -3, -2, 1] bo'ladi va bu yerda oxirgi manfiy qiymat 3-elementda (-2) joylashgan — demak, q = 3 bo‘ladi.
Nusrat shu q ni iloji boricha kichikroq son qilmoqchi. Lekin hozir Nusrat judayam erinchoq bo'lib qolgan aslida u bu vazifani bajara oladi lekin bunga erinyapti shu uchun sizning yordamingizga muhtoj. Sizning vazifangiz qaysi kombinatsiyadagi q soni eng kichik bo'lsa shu massivni topishda Nusratga yordam berishdan iborat.
T - testlar soni \(1<=T<=1000\)
keyin T marta:
N-> A va p massivlar uzunligi \(1<=N<=100\)A-> butun sonlardan iborat N uzunlikdagi massiv \(-10^9<= A <= 10^9\)p-> 0 va 1 lardan iborat N uzunlikdagi ikkilik massiv
masalada so`ralgan narsani chop eting
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 3 1 3 2 0 0 0 5 0 1 -4 6 3 0 0 0 1 1 |
1 2 3 -4 0 1 6 3 |
1-testda massivdagi har bir elementni o`zgartirishimiz mumkin ekan.
Bu holatda biz 1 2 3 variantini oladigan bo`lsak pref = [1, 3, 6] 3-son bunda maximal bo`ladi. Bu testda manfiy sonlar bo`lmagani uchun masalani asl mohiyati bu yerda ko`rinmayapti. Demak massivni har bir elementi musbat son bo`ladigan bo'lsa bizda istalgan massiv yechin bo'lolishi mumkin ekan
2-testda esa biz faqat birinchi uchta element — ya’ni 0, 1, va -4 sonlarini o‘zaro almashtirish huquqiga egamiz. Chunki aynan shu elementlar P massivida 0 ga mos keladi, ya’ni ular "erkin".
To‘rtinchi (6) va beshinchi (3) elementlar esa qulflangan bo‘lib, o‘z joyidan siljitib bo‘lmaydi.
Bu uchta erkin sonni shunday tartibda joylashtirish kerakki, prefix yig‘indilar orasida manfiy qiymat iloji boricha kam va erta tugaydigan bo‘lsin. Eng optimal joylashtirish:-4 0 1 6 3
Bu holatda prefixlar quyidagicha bo‘ladi:
p1 = -4
p2 = -4 + 0 = -4
p3 = -4 + 0 + 1 = -3
p4 = -3 + 6 = 3
p5 = 3 + 3 = 6
Bu yerda manfiy bo‘lib qoladigan eng oxirgi prefix p3 (ya'ni 3-pozitsiya). Demak, q = 3 bo‘ladi.
Agar boshqa tartiblarni sinab ko‘rsak, q bundan katta bo‘lishi mumkin, shuning uchun bu variant eng optimal natija hisoblanadi.
Telegram kanalimizga obuna bo'ling