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

# 例题

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

0 条评论

• ### Maven安装配置详细教程

你还在为导入jar包而苦恼吗？常常找不到jar包，不知道从哪导入，就算导入了可能还会依赖冲突，目录杂乱，那么maven你值得拥有。 什么是jar包？jar [...

• ### 贪心-HDU3348 coins(钱币问题)

分别给出1，5，10，50，100角面值的纸币张数，求凑出p角的最小张数和最大张数。

• ### POJ-2356 Find a multiple(DFS,抽屉原理)

Find a multiple Time Limit: 1000MS Memory Limit: 65536K Total Submissio...

• ### poj-1007-DNA Sorting

One measure of ``unsortedness'' in a sequence is the number of pairs of entries ...

• ### 【Codeforces】1213C - Book Reading

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 3.1.2 使用绘图API绘制Contour的思路

A week or so back I wrote about a package I ported/modified to create the Delaun...

传统的数据摘要包括data exploration/data cleansing/data integration.而之后,data management和bi...

• ### 生物信息学算法之 Python 实现|Rosalind 刷题笔记：007 兔子问题和递推

递推关系是一种用来定义序列的方法，可以通过前面的项，推导出后面的项。如斐波那契兔子问题，某月的兔子数，等于上一个月的兔子数，加上新生的兔子数；一个关键的现象是，...

• ### Understanding a Kernel Oops!

Understanding a kernel panic and doing the forensics to trace the bug is conside...