#709. 接水问题 Ⅱ

接水问题 Ⅱ

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

学校里有一个水房,水房里一共装有 m\red{m} 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1\red{1}

现在有 n\red{n} 名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从 1\red{1}n\red{n} 编号,i\red{i} 号同学的接水量为 wi\red{w_i}。接水开始时,1\red{1}m\red{m} 号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学j\red{j} 完成其接水量要求wj\red{w_j} 后,下一名排队等候接水的同学k\red{k}马上接替j\red{j} 同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j\red{j} 同学第x\red{x} 秒结束时完成接水,则k\red{k} 同学第x+1\red{x+1} 秒立刻开始接水。若当前接水人数n\red{n’}不足m\red{m},则只有n\red{n’}个龙头供水,其它mn\red{m−n}’个龙头关闭。

现在给出 n\red{n} 名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

输入格式

1\red12 \red2 个整数n\red{n}m\red{m},用一个空格隔开,分别表示接水人数和龙头个数。

2 \red2n\red{n} 个整数w1w2wn\red{w_1、w_2、……、w_n},每两个整数之间用一个空格隔开,wi\red{w_i} 表示i\red{i} 号同学的接水量。

输出格式

只有一行,1\red{1} 个整数,表示接水所需的总时间。

样例

输入样例1

5 3
4 4 1 2 1

输出样例1

4

输入输出样例1说明

1\red1 秒,3\red3 人接水。第1\red1 秒结束时,123\red{1、2、3 }号同学每人的已接水量为13\red{1,3} 号同学接完水,4\red4 号同学接替3\red3 号同学开始接水。

2\red2 秒,3\red3 人接水。第2\red2 秒结束时,12\red{1、2} 号同学每人的已接水量为24\red{2,4} 号同学的已接水量为1\red1

3\red3 秒,3\red3 人接水。第3\red3 秒结束时,12\red{1、2} 号同学每人的已接水量为34\red{3,4} 号同学的已接水量为2\red24\red4 号同学接完水,5\red5 号同学接替4\red4 号同学开始接水。

4\red4 秒,3\red3 人接水。第4\red4 秒结束时,12\red{1、2} 号同学每人的已接水量为45\red{4,5} 号同学的已接水量为1\red1125\red{1、2、5} 号同学接完水,即所有人完成接水。

总接水时间为4\red4 秒。

样例输入2

8 4
23 71 87 32 70 93 80 76

样例输出2

163

数据范围与提示

1n10000, \red{1 \leq n \leq 10000, }

1m100,mn, \red{1 \leq m \leq 100,m \leq n,}

1wi100 \red{1 \leq wi \leq 100}

添胜中级班(贪心)

未参加
状态
已结束
规则
IOI
题目
7
开始于
2023-8-1 12:00
结束于
2023-8-2 18:00
持续时间
30 小时
主持人
参赛人数
29