网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P1031
2024-07-17
题解 P1031 [NOIP2002 提高组] 均分纸牌
link贪心题中描述每一堆牌只能移动若干张牌到相邻的牌堆上确定了局部最优解必定能推导出全局最优解。易知均分完后,每堆牌的数量都为纸牌总数的平均数\(\mathrm{arg}\)。所以我们可以预处理每堆牌跟\(\mathrm{arg}\)的差距for(inti=1;i<=n;++i)sum+=a[i];
2024-07-17
P1031 [NOIP2002 提高组] 均分纸牌
简单贪心题。如果每个数相等时的数为sum,考虑一个数不等于sum,最好的情况通过一次转移使它变为sum。所以按顺序处理,当前数少从后面拿,当前数多向后面扔,中间记录次数即可。考虑正确性,有人会觉得,如果后面的数不够拿成为了负数,需要从更后面拿,就不止一次转移了。其实,如果遇到上述情