题目描述

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

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

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

输入描述:

第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数。
第2行n个整数，每两个整数之间用一个空格隔开，表示i号同学的接水量。

输出描述:

输出只有一行，1个整数，表示接水所需的总时间。

示例1

输入
5 3
4 4 1 2 1
输出
4
说明
第1 秒，3 人接水。第 1秒结束时，1、2、3 号同学每人的已接水量为 1，3 号同学接完水，4 号同学接替 3 号同学开始接水。
第2 秒，3 人接水。第 2 秒结束时，1、2 号同学每人的已接水量为 2，4 号同学的已接水量为 1。
第3 秒，3 人接水。第 3 秒结束时，1、2 号同学每人的已接水量为 3，4 号同学的已接水量为 2。4号同学接完水，5 号同学接替 4 号同学开始接水。
第4 秒，3 人接水。第 4 秒结束时，1、2 号同学每人的已接水量为 4，5 号同学的已接水量为 1。1、2、5 号同学接完水，即所有人完成接水。
总接水时间为4 秒。

示例2

输入
8 4
23 71 87 32 70 93 80 76
输出
163

备注:

且；
。

解答

  • 首先一定要强调的是：这个题不需要排序来做！不需要排序来做！这道题的接水顺序就是输入的顺序，并不需要再去sort贪心（不过我好像贪心也贪错啦qwq）
  • 然后看题，我们完完全全的进行模拟：使用while循环来模拟接水时间，定义一个t表示已经接完水或者正在接水的人数（好像也可以理解为现在等待接水的人的编号），while循环的停止条件是t<=n+1（这里表示前n个人都已经接完水了的情况，至于为什么，要看for循环模拟的水龙头才能解释清楚）
  • 然后在while循环里，模拟水龙头接水的情况用for（1~m）分别表示1~m个水龙头，然后用数组（其实可以再开一个数组但是我比较懒直接用w了）表示当前第i个水龙头的状态（记录还需要接多少水），显然当w[i]==0时说明接水完成了，那么就让下一个排队的人t来接水，直接使w[i]=w[t]；然后t++；表示排队的人变成下一个啦。这样每经过一次while循环，就表示接了1s的水，当最后一个等待的人也开始接水（也就是t=n+1）的时候，我们可以停止循环（反正我是这么做的）。
  • 然后显然最后一个人才刚开始接水，我们肯定不能直接停止，还要等没接完水的接完才算都接完水。所以一个for循环1~m，求出其中剩余时间最多的一个加到时间里去，输出就好辣。撒花✿✿ヽ(°▽°)ノ✿
code: 
#include<bits/stdc++.h>

using namespace std;

int n,w[11000],m,ans,maxx;

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
      scanf("%d",&w[i]);
    int t=m+1;
    while(t<=n+1){
        for(int i=1;i<=m;i++){
          w[i]--;
          if(w[i]==0){
             w[i]=w[t];
            t++;
          }
        }
        ans++;
    }
    for(int i=1;i<=m;i++)
        maxx=max(maxx,w[i]);
        
    cout<<ans+maxx<<endl;
}


来源：Sweetness