组合数学-抽屉原理

文章目录

• 抽屉原理
• 例题
• • HDU-1205
  • POJ-2356

抽屉原理

抽屉原理又称鸽巢原理：把 n+1个物品放进 n个盒子里，那么至少有一个盒子包含两个及以上的物品。

例题

HDU-1205

HDU-1205 吃糖果

Problem Description HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种，这样；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下。 Input 第一行有一个整数T，接下来T组数据，每组数据占2行，第一行是一个整数N（0<N<=1000000)，第二行是N个数，表示N种糖果的数目Mi(0<Mi<=1000000)。 Output 对于每组数据，输出一行，包含一个"Yes"或者"No"。 Sample Input 2 3 4 1 1 5 5 4 3 2 1 Sample Output No Yes

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	cin >> t;
	while (t--) {
		ll mx, x, cnt = 0;
		cin >> n >> mx;
		cnt += mx;
		for (int i = 1; i < n; i++) {
			cin >> x;
			mx = max(mx, x);
			cnt += x;
		}
		if (cnt - mx < mx - 1) cout << "No\n";
		else cout << "Yes\n";
	}
	return 0;
}

POJ-2356

POJ-2356 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

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100005;
int a[maxn], sum[maxn], vis[maxn];
int main() {
	int n;
	while (cin >> n) {
		memset(vis, -1, sizeof(vis));
		sum[0] = vis[0] = 0;	//余数为0时一个即可，置为非-1
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum[i] = (sum[i - 1] + a[i]) % n;
		}
		for (int i = 1; i <= n; i++) {
			if (vis[sum[i]] == -1)
				vis[sum[i]] = i;
			else {	//找到两个余数相同的
				cout << i - vis[sum[i]] << "\n";
				for (int j = vis[sum[i]] + 1; j <= i; j++)
					cout << a[j] << "\n";
				break;
			}
		}
	}
	return 0;
}

这一题的变形还有很多，都是抽屉原理，换汤不换药： POJ-3370 Halloween treats HDU-3183 A Magic Lamp HDU-5776 sum

原创不易，请勿转载（本不富裕的访问量雪上加霜 ） 博主首页：https://blog.csdn.net/qq_45034708