【POJ】2356 - Find a multiple（抽屉原理 & STL）

点击打开题目

Find a multiple

Description

The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k).

Input

The first line of the input contains the single number N. Each of next N lines contains one number from the given set.

Output

In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order. If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them.

Sample Input

5
1
2
3
4
1

Sample Output

2
2
3

Source

Ural Collegiate Programming Contest 1999

先说明一点，这里找若干个数，是连续的。

根据抽屉原理，不可能存在输出 0 的情况，证明如下：

用一个数组 sum[] 记录从 num[ 1 ] + num [ 2 ] + ... + num [ i ] 的值。

把每一个 sum 都对 n 求余，最后有 n 个余数，范围是 1 ~ n - 1 ，所以肯定至少有两个余数相等。证明完毕。

下面是搜解的过程：

用vector记录余数的个数与位置。

sum [ endd ] - sum [ st ] 对 n 求余是0，也就是说：sum [ st + 1 ] + sum [ st + 2 ] + ,,, + sum [ endd ] 是n的倍数。

从num [ st + 1 ] 输出到 num [ endd ] 即可。

代码如下：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	int st,endd;
	int num[10011];
	int sum[10011];
	while (~scanf ("%d",&n))
	{
		vector<int> pos[10000+11];
		sum[0] = 0;
		for (int i = 1 ; i <= n ; i++)
		{
			scanf ("%d",&num[i]);
			sum[i] = sum[i-1] + num[i];
			pos[sum[i] % n].push_back(i);
		}
		if (pos[0].size() > 0)
		{
			st = 1;
			endd = pos[0][0];
			printf ("%d\n",endd-st+1);
			for (int i = st ; i <= endd ; i++)
				printf ("%d\n",num[i]);
		}
		else		//利用抽屉原理，肯定有两个余数相等，这两个数中间的数（左开右闭）就是结果 
		{
			for (int i = 1 ; i < n ; i++)
			{
				if (pos[i].size() > 1)
				{
					st = pos[i][0] + 1;		//（左开右闭区间） 
					endd = pos[i][1];
					printf ("%d\n",endd-st+1);
					for (int i = st ; i <= endd ; i++)
						printf ("%d\n",num[i]);
					break;
				}
			}
		}
	}
	return 0;
}