证明: 设糖果有T种, 每一种有X1,X2,X3,......XT 个。
步骤一: 取X1,X2,X3........XT 中最小值Xmin。(即标准地每种吃一个,直到把最少的那一组吃完)
那么接下来剩余的糖果种类为T - 1。每一种有X1-Xmin1,X2-Xmin1,X3-Xmin1.......XT-Xmin1 个
步骤二:在剩余的T-1种糖果中,找出数量最少的。(即X1-Xmin,X2-Xmin.......XT-Xmin中最少的)
那么剩余的糖果种类为T-2,每一种有X1-Xmin1-Xmin2,X2-Xmin1-Xmin2.......XT-Xmin1-Xmin2个
重复以上步骤直到最后只剩一种糖果,这个糖果的数量为,Xmax - Xmin1- Xmin2 - Xmin3 ....- Xmin(T-1)
当这个糖果的数量为0的情况下,就可以吃完。不为0的情况下就不可以吃完。
考虑最差情况,即每一次只吃最多的一种糖果和最少的一种糖果。(每次吃2种,其他糖果不吃)
那么最后剩余糖果的数量为 Xmax - X1-X2 -X3 ....-XT
当这个值为1时 则可以吃完。大于1时 则吃不完。
接下来编程就非常容易了。
遍历一遍T组糖果中每种糖果的数量,然后算一下就行了。
是,你程序的问题就是 int num[maxn]这句话,这句话会造成堆栈溢出,它分配不了这么大的空间。解决方法:
我觉得这个题目的考点就在这个大空间的上面。我还没有编,不过我觉得你可以考虑不存储这个大的数组,只处理当前输入的数字。
你可以观察一下给的两组数据,第一组4 1 1 , 4比剩下的数的和要大两个,所以如果把4当成一个,其他全部当成一个,那一边拿一个会导致4这边,最少剩一个,也就是先拿会剩一个。
所以,我觉得可以下这个结论,这对数中最大的数,比除他以外的其他数的和大2,那就是no。其他的我觉得都是yes。
所以,可以这么编。
输入n
for i = 1 ~ n
{
max
sum
输入kind
for j = 1~ kind
{
输入当前的数input
max 用来找到这堆数中最大的数
sum 用来记录总和。不过要注意sum也可能超,如果可以申明__int64类型就很简单了
}
if( (max - (sum-max)) >=2 ) 输出 no
else 输出 yes
}