首页 > ACM题库 > HDU-杭电 > HDU 1205 吃糖果-组合数学-[解题报告] C++
2013
12-04

HDU 1205 吃糖果-组合数学-[解题报告] C++

吃糖果

问题描述 :

HOHO,终于从Speakless手上赢走了所有的糖果,是Gardon吃糖果时有个特殊的癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另一种,这样;可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完?请你写个程序帮忙计算一下。

输入:

第一行有一个整数T,接下来T组数据,每组数据占2行,第一行是一个整数N(0<N<=1000000),第二行是N个数,表示N种糖果的数目Mi(0<Mi<=1000000)。

输出:

对于每组数据,输出一行,包含一个"Yes"或者"No"。

样例输入:

2
3
4 1 1
5
5 4 3 2 1

样例输出:

No
Yes

Hint
Hint
Please use function scanf

还是有点心急了。

思路对了,发现如果有其中一种糖果是大于总数量的一半-1,那么将会无法形成隔板

1.样例:[4,1,1] 就是对应这种情况—>  |`|`| |,发现,如果当中出现一种类型,总数除去这部分剩下的部分要形成隔板才行,至少是sum-ele+1>=ele

2.因此,对于每次输入的数,找出最大的数,并确定是否大于数量的一半-1即可。

3.看了一些题解是属于抽屉原理。不太懂,学一下。

 

#include <stdio.h>
 
 __int64 num;
 
 int main()
 {
     __int64 sum=0;
     int T,n;
     scanf("%d",&T);
     while(T--)
     {
         int flag = 0;
         sum=0;
         scanf("%d",&n);
         __int64 max = 0;
         for(int i=0;i<n;i++) 
         {
             scanf("%I64d",&num);
             sum += num;
             if(max < num) max = num;
         }
         printf(sum-max+1>=max ? "Yes\n" : "No\n");
     }
     return 0;
 }

 

 

 

 


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }