题目
题目描述
学校里有一个水房，水房里一共装有个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为。
现在有名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 到编号，号同学的接水量为 。接水开始时，到 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学完成其接水量要求后，下一名排队等候接水的同学 马上接替 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 同学第 秒结束时完成接水，则 同学第 秒立刻开始接水。若当前接水人数 ’不足 ，则只有 ’个龙头供水，其它 ’个龙头关闭。
现在给出 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
输入格式
第 行 个整数 和 ，用一个空格隔开，分别表示接水人数和龙头个数。
第 行 个整数，每两个整数之间用一个空格隔开，表示号同学的接水量。
输出格式
个整数，表示接水所需的总时间。
输入输出样例
5 3 4 4 1 2 1
4
8 4 23 71 87 32 70 93 80 76
163
说明/提示
【输入输出样例 1 说明】
第 秒，人接水。第 秒结束时，号同学每人的已接水量为 号同学接完水，号同学接替 号同学开始接水。
第 秒，人接水。第 秒结束时，号同学每人的已接水量为 号同学的已接水量为。
第 秒，人接水。第 秒结束时， 号同学每人的已接水量为 号同学的已接水量为2。 号同学接完水， 号同学接替号同学开始接水。
第 秒，人接水。第 秒结束时， 号同学每人的已接水量为 号同学的已接水量为。 号同学接完水，即所有人完成接水的总接水时间为 秒。
【数据范围】
且；
。
实现
这题乍一看会用模拟来做，一秒一秒得模拟，而这种方法实在太慢，有一个好办法，那就是把正在使用水龙头的剩余最少的剩余水量作为每一次模拟的时间，而非一秒一秒模拟。
具体思路是首先输入，将前个赋值到水龙头()的结构体数组中，排序。接下来while循环，当所有人都开始接水时结束，while循环内负责计算时间总和，每次加上剩余最少的那个的水量，负责记录那个人的剩余水量（如果不加后面就不对了，原变量会被覆盖）。while循环中for循环，将每个水量都减去，if语句负责将没有剩余，也就是接好的人替换到下一个，负责记录下一个等待加水的人。while循环最后，排序。while循环结束，意味着所有人都在接水或已经接好水，此时，只需加上在加水的人中剩余最多的水量即可。
说干就干，很快就可以写出如下代码:
#include <bits/stdc++.h>
using namespace std;
int n,m;
int w[10005];
typedef struct node{
int water;
int number;
}node;
node slt[105];
int now=0;
int time1 = 0;
int jian;
bool cmp(node a,node b){
return a.water < b.water;
}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
cin >> w[i];
}
for(int i = 0; i < m; i++){
slt[i].water = w[i];
slt[i].number = i;
}
now = m;
sort(slt,slt+m,cmp);
while (now<=n){
time1+=slt[0].water;
jian = slt[0].water;
for(int i = 0; i < m; i++){
slt[i].water -= jian;
if(slt[i].water<=0){
slt[i].water=w[now];
slt[i].number=now;
now++;
}
}
sort(slt,slt+m,cmp);
}
sort(slt,slt+m,cmp);
time1 += slt[m-1].water;
cout << time1;
return 0;
}
主要讲一下几个坑点：
- while循环里的条件
- while循环中累加的位置
- 最后的加法不能忘。