poj2356

文章目录

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

抽屉原理

抽屉原理又称鸽巢原理：把 n + 1 n+1 n+1个物品放进 n n 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

用”隔板法“选最大的糖果数 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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
#include
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;
}

今天的文章poj2356分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。