hdu 1205 吃糖果 （鸽笼原理）
http://acm.hdu.edu.cn/showproblem.php?pid=1205 题意：有n种糖果，第i种糖果有a[i]个，相邻两次不能吃一样的糖果，问能否有办法吃完所有糖果… 思路：如果第i种糖果有k个的话，那么其他所有种类的糖果之和至少有k-1个，才可能吃完。复杂度O(n) 看到有人说是抽屉原理…..大概。。。？不过不太明显。。直接想就好吧
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月29日 星期一 20时40分00秒
4File Name :code/hdu/1205.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E6+7;
34int n;
35LL a[N];
36LL total;
37
38int main()
39{
40 #ifndef ONLINE_JUDGE
41 freopen("code/in.txt","r",stdin);
42 #endif
43
44 ios::sync_with_stdio(false);
45 int T;
46 cin>>T;
47 while (T--)
48 {
49 cin>>n;
50 total = 0;
51 for ( int i = 1 ; i <= n ; i++)
52 {
53 cin>>a[i];
54 total +=a[i];
55 }
56
57
58
59 bool ok = true;
60 for ( int i = 1 ; i <= n ; i++)
61 {
62 LL x;
63 x= total-a[i];
64 if (x<a[i]-1)
65 {
66 ok = false;
67 break;
68 }
69 }
70
71 if (ok)
72 {
73 puts("Yes");
74 }
75 else
76 {
77 puts("No");
78 }
79
80 }
81
82 #ifndef ONLINE_JUDGE
83 fclose(stdin);
84 #endif
85 return 0;
86}