程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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
2
3
4 1 1
5
5 4 3 2 1
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;
}

 

 

 

 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved