程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 1205 吃糖果(鴿巢原理)

hdu 1205 吃糖果(鴿巢原理)

編輯：關於C++

Problem Description HOHO，終於從Speakless手上贏走了所有的糖果，是Gardon吃糖果時有個特殊的癖好，就是不喜歡將一樣的糖果放在一起吃，喜歡先吃一種，下一次吃另一種，這樣；可是Gardon不知道是否存在一種吃糖果的順序使得他能把所有糖果都吃完？請你寫個程序幫忙計算一下。
Input 第一行有一個整數T，接下來T組數據，每組數據占2行，第一行是一個整數N（0 Output 對於每組數據，輸出一行，包含一個Yes或者No。
Sample Input

Sample Output

No
Yes

【思路】：

1.把某種糖果看做隔板,如果某種糖果有n個,那麼就有n+1塊區域,至少需要n-1塊其他種糖果才能使得所有隔板不挨在一塊..也就是說能吃完這種糖果.至少需要其他種類糖果n-1塊..(鴿巢原理)

2.數量最多的糖果(隔板)可以構造最多的空間,如果這種糖果有maxn個....那麼需要maxn-1個其他種糖果.對於某種數量少於maxn的糖果來說,可以在原本數量最多的糖果構造的隔板上加厚原有的隔板...,那麼這某種糖果就銷聲匿跡了.....

考慮極端情況.如果某種糖果無法在這maxn+1的空間內構造出符合條件的序列,那麼這種糖果至少要有maxn+1+1個(考慮只有兩種糖果的情況)...(鴿巢原理)...但是這與數量最多的那種糖果只有maxn個矛盾.....(maxn+1+1>maxn 這不等式不難理解吧....). 來源：大神博客

最多的糖有max，剩下的糖 = sum-max；

就是說只要剩下的糖能把數量最多的糖max分隔開就能滿足條件，其余的糖因為數量小於max，所以可以插入之前 max分割後組成的序列

MMMMM NNNN BBBB VVV CC X

M N M N M N M N M
數目最多的M被分隔後。

M N B M N B M N B M N B M 這個時候 B選擇插入的位置就有很多種了，因此，只要滿足數目最大的糖能被分隔開，就能使所有的糖滿足條件；

【代碼如下：】

#include 
#include 
#include 
#define maxn 1000000+10
using namespace std;
typedef long long ll;//注意sum的極限情況可達到1000000*1000000= 1e12，超過了int的表示范圍
ll num[maxn];
int main()
{
    int t;
    scanf(%d,&t);
    while(t--)
    {
        int n;
        ll sum=0,max=0;
        scanf(%d,&n);
        for(int i=0;imax)
                max=num[i];
            sum+=num[i];
        }
        if(sum-max>=max-1)
            printf(Yes
);
        else
            printf(No
);
    }
    return 0;
}