原题地址点 这里
这是一道应用的贪心策略的题目。
在知道各摞纸牌数量后，可以计算出纸牌的平均高度，也就是最后均分后的高度。
然后具体的贪心算法为：
顺序遍历每一张纸牌。如果当前纸牌高度刚好为均分后的高度，则继续遍历下一张。如果当前纸牌数多余或少于均分高度，则向下一摞添加或借出差的纸牌，哪怕会令下一摞纸牌高度变成负数也这么做，然后将移动次数加一。到最后一摞纸牌时，只要题目保证有解，则此时所有纸牌高度一定等于均分高度。但是为什么这种看似奇怪的方法能得出正确的结果呢？（以后有时间再把坑填上~）
最终代码如下：
#include <cstdio>#include <numeric>using namespace std;const int maxn= 105;int cnt[maxn], size, ans=0;int main(){ scanf("%d", &size); for(int i=0; i<size; ++i){ scanf("%d", &cnt[i]); } int ave= accumulate(cnt, cnt+size, 0)/size; for(int i=0; i<size; ++i){ int &now= cnt[i], &next= cnt[i+1]; if(now!=ave){ next-= ave-now; ++ans; } } PRintf("%d/n", ans); return 0;}新闻热点
疑难解答
