Problem 7C. 分发物资

Problem 7C. 分发物资

Problem 7C. 分发物资

题目描述

现在数轴的 1,2,n1,2\cdots ,n 处各有一个人,他们各需要 a1,a2,,ana_1,a_2,\cdots ,a_n 的物资。

因此,你准备了 m=i=1naim=\sum_{i=1}^n a_i 份物资准备分发。

给定参数 kk,你可以进行以下操作:

  • 花费 11 的时间,选择一段区间 [l,r][l, r],且满足1lrn1\le l\le r\le nrl+1kr-l+1\le k并且你的剩余物资数至少要有 rl+1r-l+1 。接下来,向数轴上位置为 l,l+1,,rl,l+1,\cdots ,r 的人各分发一份物资。

求至少需要多少时间,才能满足所有人的需求。

输入格式

第一行两个整数 n,kn,k,表示需要分发的人数和每次最多分发的人数。

第二行 nn 个整数 aia_i,表示每个人需要物资的份数。

输出格式

仅一个整数,表示至少需要的时间。

样例输入1

4 2
1 4 2 1

样例输出1

样例1解释

每次至多分发给连续的两个人。

操作如下:

1 1 0 0

1 2 2 0

1 3 2 0

1 4 2 0

1 4 2 1

样例输入2

7 4
1 5 2 4 2 4 2

样例输出2

数据范围与约定

对于 40%40\% 的数据,n=k=2n=k=2

对于另外 20%20 \% 的数据,k=nk=n

对于另外 20%20\% 的数据,1n,ai1001\le n,a_i\le 100

以上三部分数据不重合,占本题 80%80\% 的分数。

对于 100%100\% 的数据,1kn5×1051\le k\le n\le 5\times 10^51ai1091\le a_i\le 10^9

注意,答案可能超过 3232 位整数可以表示的范围。

信息

ID
1552
难度
10
分类
(无)
标签
(无)
递交数
17
已通过
0
通过率
0%
上传者

相关

在下列训练计划中:

2023秋 悬赏令题单

在下列比赛中:

2023秋 悬赏令第七周