HDU 1205.キャンディを食べる【ハトの巣の原理】【8月1】
あめを食べる
Problem Description
HOHO、ついにSpeaklessの手からすべてのキャンディに勝って、Gardonがキャンディを食べる時特殊な癖があって、同じキャンディを一緒に食べるのが好きではありませんて、先に1種を食べるのが好きで、次は別の種を食べて、このようにします;しかし、Gardonはキャンディを食べる順番があるかどうか分からない.彼はすべてのキャンディを食べ終わることができるのだろうか.プログラムを書いて計算してください.
Input
1行目には整数Tがあり、次にT組のデータが2行を占め、1行目は整数N(0
Output
データのセットごとに、「Yes」または「No」を含む行を出力します.
Sample Input
Sample Output
この問題は、自分では思いもよらなかった~~~こんな原理もある.
考え方:ハトの巣の原理
証明:
1.あるキャンディを仕切り板と見なし、あるキャンディがn個あればn+1個の領域があり、少なくともn-1個の他のキャンディが必要である.
すべての仕切り板を1つにしないようにすることができます.つまり、このキャンディを食べ終わることができます.少なくとも他の種類のキャンディn-1枚が必要である.(ハトの巣の原理)
2.最も多い数のキャンディ(仕切り板)は最も多くの空間を構築することができて、もしこのキャンディがmaxn個あるならば....ではmaxn-1個が必要です
彼はキャンディを栽培する.ある種の数がmaxnより少ないキャンディにとって、本来最も数の多いキャンディ構造の仕切り板に「厚くする」ことができる.
ある仕切り板は...、では、この「あるキャンディ」は姿を消しました.....すなわち,maxnに対して,残りのsum−maxn>=maxn−1であれば,必ず完食できる.式整理変形:sum-2*maxn-1>=0(変形せずに直接式を置いてもよい).
もう一つの注意点は、数値sumがintを超える可能性があるのでlong longを使用します.コードは次のとおりです.
もし最大の山-次の山<=1ならば、问题はきっと解があります:私达は最大と次の大きい中から毎回1つを持って、それから彼らが第3の山と等しい时を待って、毎回3つの山の中からそれぞれ1つを持って、彼らが第4の山と等しい时を待って、毎回4つの山の中からそれぞれ1つを持って、このようにずっとすべての山を持っています.問題は最大ヒープ-次ヒープ<=1にできるかどうかということになったので,以前は次ヒープ以外のヒープから取って最大ヒープを減らすことができ,最大ヒープ-次ヒープ<=1に減らすことができれば,原問題は解決する.要看:sum-max-max-max 2>=max-max-max 2-1が成立するかどうか、sumが総和、maxが最大スタック、max 2が次大である.整理:2*max-sum<=1
推理してみると、上の公式と同じですね~
Problem Description
HOHO、ついにSpeaklessの手からすべてのキャンディに勝って、Gardonがキャンディを食べる時特殊な癖があって、同じキャンディを一緒に食べるのが好きではありませんて、先に1種を食べるのが好きで、次は別の種を食べて、このようにします;しかし、Gardonはキャンディを食べる順番があるかどうか分からない.彼はすべてのキャンディを食べ終わることができるのだろうか.プログラムを書いて計算してください.
Input
1行目には整数Tがあり、次にT組のデータが2行を占め、1行目は整数N(0
Output
データのセットごとに、「Yes」または「No」を含む行を出力します.
Sample Input
2
3
4 1 1
5
5 4 3 2 1
Sample Output
No
Yes
Hint
Hint
Please use function scanf
この問題は、自分では思いもよらなかった~~~こんな原理もある.
考え方:ハトの巣の原理
証明:
1.あるキャンディを仕切り板と見なし、あるキャンディがn個あればn+1個の領域があり、少なくともn-1個の他のキャンディが必要である.
すべての仕切り板を1つにしないようにすることができます.つまり、このキャンディを食べ終わることができます.少なくとも他の種類のキャンディn-1枚が必要である.(ハトの巣の原理)
2.最も多い数のキャンディ(仕切り板)は最も多くの空間を構築することができて、もしこのキャンディがmaxn個あるならば....ではmaxn-1個が必要です
彼はキャンディを栽培する.ある種の数がmaxnより少ないキャンディにとって、本来最も数の多いキャンディ構造の仕切り板に「厚くする」ことができる.
ある仕切り板は...、では、この「あるキャンディ」は姿を消しました.....すなわち,maxnに対して,残りのsum−maxn>=maxn−1であれば,必ず完食できる.式整理変形:sum-2*maxn-1>=0(変形せずに直接式を置いてもよい).
もう一つの注意点は、数値sumがintを超える可能性があるのでlong longを使用します.コードは次のとおりです.
#include<cstdio>
int main()
{
int T,maxn,n,x;
long long sum;
scanf("%d",&T);
while(T--){
maxn=sum=0;
scanf("%d",&n);
while(n--){
scanf("%d",&x);
sum+=x;
if(x>maxn) maxn=x;
}
if(sum-2*maxn+1>=0) printf("Yes
");
else printf("No
");
}
return 0;
}
もし最大の山-次の山<=1ならば、问题はきっと解があります:私达は最大と次の大きい中から毎回1つを持って、それから彼らが第3の山と等しい时を待って、毎回3つの山の中からそれぞれ1つを持って、彼らが第4の山と等しい时を待って、毎回4つの山の中からそれぞれ1つを持って、このようにずっとすべての山を持っています.問題は最大ヒープ-次ヒープ<=1にできるかどうかということになったので,以前は次ヒープ以外のヒープから取って最大ヒープを減らすことができ,最大ヒープ-次ヒープ<=1に減らすことができれば,原問題は解決する.要看:sum-max-max-max 2>=max-max-max 2-1が成立するかどうか、sumが総和、maxが最大スタック、max 2が次大である.整理:2*max-sum<=1
推理してみると、上の公式と同じですね~