P1190 [NOIP2010 普及组] 接水问题

解释一下题目

从一个长度为N的队列（就是平常排的队），里选出M个人来到洗手池，只要有一个人洗完手了，m+1号位的人就会来替补他.循环往复直到后面没有替代的人,输出最后的时间.

想到这道题你肯定会用暴力枚举,我也尝试过用暴力枚举但是如果用数组的话有很多难题需要你解决,我们可以运用一下简单的贪心算法.

1.道理

贪心算法

1.从教室角度看贪心算法

下面是课程表

如果我们想尽量上多的课，而且两节课不能重复上，比如你上美术课有上英语课美术课下课的时候英语课已经上课了所以不能边上美术课边上英语课。

1.选出结束最早的课

他就是要在这间教室里上的第一堂课美术课上午十点结束时间最早因此美术课是第一堂课。

2.接下来必须选出第一堂课结束后才开始的课程

这样选择结束最早的课这将是要在这间教室上的第二节课及计算机课

重复刚才两个步骤，就可以得知答案，结果为“美术，计算机，音乐”。

这是一个简单的贪心算法。

2.开始实践调整思路

1.思路

输入的W序列中,取出前m个数字,查找其中最小的数字,将后面的数字加到最小的数字之上,循环往复,循环到N,在找出这个数列中数最大的数字,最后输出,就是这一道题的答案.

2.实践

输入

#include <algorithm>
#include <iostream>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	int num[n+10];
	
	int b = 0;
	for (int i=0; i < n; i++){
		cin >> num[i];
		if (num[i] >= b){
			b = num[i];
		}
	}
}

B这个变量是为了储存列表中时间的最大值,你可以不写b,主要是我后面有一个特判程序.

核心程序

方法一:

求最小值用sort函数(不太推荐,毕竟排序可能会用到双重循环,您也不知道他是怎么写的)


	if (n == m){
		cout << b;
		return 0;
	}
	for (int i=m; i < n; i++){
		sort(num,num+m);
		
		num[0] += num[i];
	}

方法二:

循环求最小值

if (n <= m){
		cout << b;
		return 0;
	}
	for (int i=m; i < n; i++){
		int s = 1000000,wei = 0;
		for (int j=0;j < m;j++){
			if (num[j] < s){
				s = num[j];
				wei = j;
			}
		}
		num[wei] += num[i];
	}

注意最小值S(初始值)得开大一点.

要不然有两个测试点wa.(洛谷里的)

输出


	b = 0;
	for (int i=0; i < n; i++){
		if (num[i] >= b){
			b = num[i];
		}
	}
	cout << b;

总体代码

#include <algorithm>
#include <iostream>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	int num[n+10];
	int mun[m+10];
	
	int b = 0;
	for (int i=0; i < n; i++){
		cin >> num[i];
		if (num[i] >= b){
			b = num[i];
		}
	}
	for (int i=0; i < m; i++){
		mun[i] = num[i];
	}
	if (n <= m){
		cout << b;
		return 0;
	}
	for (int i=m; i < n; i++){
		int s = 1000000,wei = 0;
		for (int j=0;j < m;j++){
			if (num[j] < s){
				s = num[j];
				wei = j;
			}
		}
		num[wei] += num[i];
	}
	b = 0;
	for (int i=0; i < n; i++){
		if (num[i] >= b){
			b = num[i];
		}
	}
	cout << b;
	return 0;
}

秒客网