【洛谷p1190】接水问题

咱也不知道为啥咱就是想写博客emmm

尽管这个题是2010年的普及组但是我太菜了并不会写emm

其实感觉这道题是纯纯正正的大模拟；

算法标签中的贪心是没有意义的啊？？【洛谷p1190】接水问题

SOLUTION:

首先一定要强调的是：这个题不需要排序来做！不需要排序来做！这道题的接水顺序就是输入的顺序，并不需要再去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;
}

end-

【洛谷p1190】接水问题

相关推荐