专栏首页程序员NOI接水问题

NOI接水问题

15:接水问题 总时间限制: 1000ms 内存限制: 65536kB 描述 学校里有一个水房,水房里一共装有 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 个整数 w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示 i 号同学的接水量。 1 ≤ n ≤ 10000,1 ≤ m ≤ 100 且 m ≤ n; 1 ≤ wi ≤ 100。 输出 输出只有一行,1 个整数,表示接水所需的总时间。 样例输入 样例 #1: 5 3 4 4 1 2 1 样例 #2: 8 4 23 71 87 32 70 93 80 76 样例输出 样例 #1: 4 样例 #2:

163

分析:我们需要求出的是“接水时间”,因此“需要求出每一次接水量”的最小值,这个人肯定是这一组接水的人之中最快接完水的。在他接完水之后,只要后面还有未接水的同学,就接着他后面接水。这样,由于新的接水人的加入,就形成了一组新的人。对这组新的接水人,又“需要求出每一次接水量”的最小值。这样一直循环下去,直到没有接水人为止。输出最大的那个数值即可。

代码如下:

#include<stdio.h>
#include<stdlib.h>

int max(int *p, int n);
int min(int *p, int n);

int main(void)
{
	int n, m, k;
	scanf("%d %d", &n, &m);
	int *p1 = (int *)malloc(sizeof(int) *n);
	int *p2 = (int *)malloc(sizeof(int) *m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &p1[i]);
	}
	for (int i = 0; i < m; i++)//先将m个人依次放到水龙头处,接水
	{
		p2[i] = p1[i];
	}
	
	k = min(p2, m);	//找到最快接完水的人。
	for (int i = 0; i < n - m; i++)
	{
		p2[k] += p1[i + m];	//最快接完水的人,后面接上别人,继续接水
		k = min(p2, m);		//继续从新的接水量里面,找到最快接完水的人。
	}
	printf("%d\n", max(p2, m));
	return 0;
}
int max(int *p, int n)
{
	//这个返回的是数字,不是下标。
	int num = p[0];
	for (int i = 0; i < n - 1; i++)
	{
		if (num < p[i + 1])
		{
			num = p[i + 1];
		}
	}
	return num;
}
int min(int *p, int n)
{
	//这里找到了最小值,但是返回的是最小值的下标,而非数字。
	int num = p[0];
	int k = 0;		//记录下标
	for (int i = 0; i < n - 1; i++)
	{
		if (num > p[i + 1])
		{
			num = p[i + 1];
			k = i + 1;
		}
	}
	return k;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT(乙级)1005

    卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里,情况稍微有些复杂。

    zy010101
  • PAT(乙级)1001

    对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n=1。卡拉兹在195...

    zy010101
  • PAT(乙级)1013

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.net/z...

    zy010101
  • 数码管问题(c++实现)

        描述:液晶数码管用七笔阿拉数字表示的十个数字,把横和竖的一 个短划都称为一笔,即7有3笔,8有7笔等。对于十个数字一种排列,要做到  两相邻数字都可以由...

    用户2038589
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • leetcode 204题求素数个数

    Count the number of prime numbers less than a non-negative number, n

    流川疯
  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • 挖掘机技术哪家强(c++实现)

    描述:为了用事实说明挖掘机技术到底哪家强,组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

    用户2038589

扫码关注云+社区

领取腾讯云代金券