组合数学-抽屉原理

迷南。 2022-11-28 13:19 295阅读 0赞

### 文章目录 ###

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

# 抽屉原理 #

--------------------

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

# 例题 #

## HDU-1205 ##

--------------------

[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

用”隔板法“选最大的糖果数 m x mx mx作为隔板形成 m x − 1 mx-1 mx−1个抽屉，若剩下的糖果数小于抽屉数，那么就会有至少两个空抽屉(糖果)挨在一起，输出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

题意：给定 n n n个数，要求找出若干数，使其和为 n n n的倍数。  
分析：用 s u m \[ \] sum\[\] sum\[\]表示前缀和，首先如果前缀和取余 n n n为0，则为答案；不然用 n n n的余数作为抽屉，除去0共 n − 1 个 n-1个 n−1个，当记录两个前缀和取余n的余数相同时，则中间这段即是答案；而由抽屉定理 n n n个数放进 n − 1 n-1 n−1个抽屉，定有一个抽屉有两个以上数；故答案一定存在。

#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][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[HDU-1205]: https://vjudge.net/problem/HDU-1205
[POJ-2356 Find a multiple]: https://vjudge.net/problem/POJ-2356
[POJ-3370 Halloween treats]: https://vjudge.net/problem/POJ-3370
[HDU-3183 A Magic Lamp]: https://vjudge.net/problem/HDU-3183
[HDU-5776 sum]: https://vjudge.net/problem/HDU-5776
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708