Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Хашаа
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Поликарпусийн гэрийн урд хашаа байдаг. Хашаа $n$ ширхэг ижил өргөнтэй нэг нь нөгөөгийхөө араас зүүнээс баруун тийш цувж байрласан банзнуудаас бүтдэг. $i$ дэх банзны өндөр $h_i$ метр, өөр банзнууд өөр өндөртэй байж болдог байна.
Зураг: $n = 7$ ба $h = [1, 2, 6, 1, 1, 7, 1]$ тохиолдол
Поликарпус дээд зэрэглэлийн төгөлдөр хуур худалдаж авсан ба үүнийгээ гэртээ хэрхэн оруулах талаар бодож байна. Төлөвлөгөөгөө гүйцэлдүүлэхийн тулд тэрээр хашаанаасаа $k$ ширхэг дараалласан банзнуудыг авах хэрэгтэй болно. Өндөр банзнуудыг хашаанаас салгаж авахад илүү хэцүү болохоор Поликарпүс өндрүүдийн нийлбэр нь байж болох хамгийн бага утга бүхий дараалласан $k$ ширхэг банзнуудыг олохыг хүсч байлаа.
Нийт өндрийн хэмжээ нь хамгийн бага байдаг $k$ ширхэг дараалласан хашаануудын индексүүдийг олдог програм бичээрэй. Хашаа Поликарпүсийн гэрийг тойроод биш гэрийнх нь урд байдгийг анхааруулъя (өөрөөр хэлбэл хашаа тойрог биш).
Оролт
Оролтын эхний мөрөнд $n$ болон $k$ ($1 ≤ n ≤ 1.5·10^5$, $1 ≤ k ≤ n$) гэсэн хашааны банзнуудын тоо болон төгөлдөр хууранд зориулж гаргах нүхний өргөнг илэрхийлэх 2 ширхэг бүхэл тоо байна. 2 дахь мөрөнд хашааны $i$ дэх банзны өндөр $h_i$ байхаар $h_1, h_2, ... , h_n$ ($1 ≤ h_i ≤ 100$) бүхэл тоонуудын дарааллууд байна.
Гаралт
$j, j+1, ... , j+k-1$ банзнуудын өндрийн нийлбэр нь боломжит хамгийн бага утгатай байх $j$-г хэвлэ. Ийм хэд хэдэн $j$ байвал тэдний аль нэгийг нь хэвлээрэй.
Орчуулсан: Энхдүүрэн
Жишээ тэстүүд
Оролт
7 3 1 2 6 1 1 7 1
Гаралт
3
Тэмдэглэл
In the sample, your task is to find three consecutive planks with the minimum sum of heights. In the given case three planks with indexes 3, 4 and 5 have the required attribute, their total height is 8.