推荐一个可以做ppt的网站,微信公众号官网登录,网站开发与维护工资,网站图片设置教程题意
学校里有一个水房#xff0c;水房里一共装有 m个龙头可供同学们打开水#xff0c;每个龙头每秒钟的供水量相等#xff0c;均为 1。
现在有 n名同学准备接水#xff0c;他们的初始接水顺序已经确定。
将这些同学按接水顺序从 1到 n编号#xff0c;i号同学…题意
学校里有一个水房水房里一共装有 m个龙头可供同学们打开水每个龙头每秒钟的供水量相等均为 1。
现在有 n名同学准备接水他们的初始接水顺序已经确定。
将这些同学按接水顺序从 1到 n编号i号同学的接水量为 wi。
接水开始时1到 m号同学各占一个水龙头并同时打开水龙头接水。
当其中某名同学 j完成其接水量要求 wj 后下一名排队等候接水的同学 k上接替 j同学的位置开始接水。
这个换人的过程是瞬间完成的且没有任何水的浪费。
即 j同学第 x秒结束时完成接水 则 k同学第 x1秒立刻开始接水。
若当前接水人数 n′不足 m则只有 n′个龙头供水其它 m−n′个龙头关闭。 现在给出 n名同学的接水量按照上述接水规则问所有同学都接完水需要多少秒。 输入格式
第 1行 2个整数 n和 m用一个空格隔开分别表示接水人数和龙头个数。
第 2行 n个整数 w1、w2、…、wn每两个整数之间用一个空格隔开wi表示 i号同学的接水量。
输出格式
输出只有一行1个整数表示接水所需的总时间。
数据范围
1≤n≤10000,
1≤m≤100,m≤n,
1≤wi≤100
输入样例
5 3
4 4 1 2 1
输出样例
4 提示以下是本篇文章正文内容下面案例可供参考 代码如下示例 #include iostream
#include cstdlib
using namespace std;
int compare(const void* a, const void* b)
{ return (*(int*)b - *(int*)a); }
int main(){int n,m;cinnm;int k[n];for(int i0;in;i){cink[i];}qsort(k,n,sizeof(1),compare);if(nm){coutk[0]endl;return 0;}int kk[m]{0};//记录每个水龙头承担的任务 for(int i0;im;i){kk[i]k[i];}int iim-1; //剩下的人在当前任务量最少的水龙头处排队int x0; //标记下标该走向0表示回退1表示前进 int maxkk[0]; //当前任务量最多的是0号水龙头 for(int im;in;i){kk[ii]k[i]; //给当前任务量最少的水龙头增加任务 if(maxkk[ii]){maxkk[ii]; //更新当前任务量最大的水龙头 if(x0){ii--;if(ii-1){x1;ii0;}}else{ii;if(iim){x0;iim-1;}}}}qsort(kk,m,sizeof(1),compare);coutkk[0]endl;
}
