АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Гүүдланд нь тодорхой тооны хоорондоо ижил зайтай хотуудтай улс юм. Зэргэлдээх хотуудын хоорондын зай нь 1 нэгж.

Энерги, эрчим хүчний бүтээн байгуулалттай холбоотой хурал болж байгаа бөгөөд засгийн газар бүх хотуудыг эрчим хүчээр

бүрэн хангахад хамгийн багадаа хэдэн ширхэг эрчим хүчний цахилгаан станц барих хэрэгтэйг мэдмээр байгаа.

Энэ тоог ол. Боломжгүй бол -1 гэсэн утгыг буцаа.

Танд хотуудын мэдээлэл жагсаалт хэлбэрээр өгөгдөнө.

Цахилгаан станц барих боломжтой хотыг 1-ээр тэмдэглэсэн ба  боломжгүй хотуудыг 0-ээр тэмдэглэсэн.

Цахилгаан станцын дээд хүртээмж k бол хамгийн багадаа хэдэн цахилгаан станц тус улсад баригдах хэрэгтэй вэ гэдгийг ол.

Хүртээмж гэдгийг өөрөөр тайлбарлавал тухайн цахилгаан станцаас k-аас бага нэгжийн зайтай хотод эрчим хүч түгээх чадалтай гэсэн үг.

Жишээ нь, танд k=3; arr=[0, 1, 1, 1, 0, 0, 0] өгөгдвөл.

Бүх хот 1 нэгжийн зайтай учраас хотуудаа 0-гээс эхлэн дугаарлая. 3  хотод цахилгаан станц барих боломжтой ба эдгээр нь 1,2,3-р хотууд юм.

Хэрвээ бид 2-р хотод цахилгаан станц барьвал 0-ээс 4-р хотууд эрчим хүчээр бүрэн хангагдана.

 0 болон 4-р хотууд нь цахилгаан станцаас 2 нэгжийн зайтай буюу энэ нь хүртээмжийн дээд хязгаар юм.

6-р хотыг эрчим хүчээр хангахын тулд  бид 4,5, эсвэл 6-р хотод цахилгаан станц барих шаардлагатай.

Харамсалтай нь эдгээр хотуудад цахилгаан станц барих боломжгүй тул бид -1 утгыг буцаах хэрэгтэй.

Өгөгдсөн хязгаарлалтуудад үндэслэн бид улсыг бүрэн эрчим хүчээр хангах боломжгүй гэсэн дүгнэлтэнд хүрлээ.

Функцийн тайлбар

Pylons гэдэг функцыг бичнэ үү. Хамгийн багадаа барих шаардлагатай цахилгаан станцын тоо болох бүхэл тоог эсвэл боломжгүй бол 1-ийг хэвлэх үүрэгтэй.

Pylon доорх өгөгдлийг хүлээн авна

·         K : бүхэл тоо ба энэ нь цахилгаан станцын дээд хүртээмжийг илэрхийлнэ.

·         Arr : Бүхэл тоон массив ба энэ нь хотуудад цахилгаан станц барих боломжтой эсэхийг илэрхийлнэ.

Оролтын бүтэц

Эхний мөрөнд бүхэл тоонууд , n ба k , Гүүдланд улсын хотын тоо ба Станцын дээд хүртээмж.

Дараагийн мөрөнд arr массив өгөгдөнө.

Хязгаарлалт

1 <= k <= n <= 10⁵

Arr [i]  {0,1}

Дэд даалгавар

1 <= k <= n <= 1,000 үед 40% оноо авна. 

Гаралтын бүтэц

Улсын бүх хотуудыг эрчим хүчээр бүрэн хангахад шаардагдах хамгийн цөөн эрчим хүчний цахилгаан станцын тоог эсвэл боломжгүй бол 1-ийг хэвлэ.

Жишээ оролт

6 2

0 1 1 1 1 0

Жишээ гаралт

2

Тайлбар

Хотууд c[1], c[2], c[3], ба c[4] нарт цахилгаан станц барих боломжтой. Цахилгаан станц бүрийн хүртээмжийн хязгаар 2.

Хэрвээ c[1] болон c[4]-т цахилгаан станц барьвал бүх хотууд эрчим хүчээр бүрэн хангагдана. Тиймээс хариу 2.

Орчуулсан : Б.Мөнхбаяр АНУ