原題地址點(diǎn) 這里
這是一道應(yīng)用的貪心策略的題目。
在知道各摞紙牌數(shù)量后，可以計(jì)算出紙牌的平均高度，也就是最后均分后的高度。
然后具體的貪心算法為：
順序遍歷每一張紙牌。如果當(dāng)前紙牌高度剛好為均分后的高度，則繼續(xù)遍歷下一張。如果當(dāng)前紙牌數(shù)多余或少于均分高度，則向下一摞添加或借出差的紙牌，哪怕會(huì)令下一摞紙牌高度變成負(fù)數(shù)也這么做，然后將移動(dòng)次數(shù)加一。到最后一摞紙牌時(shí)，只要題目保證有解，則此時(shí)所有紙牌高度一定等于均分高度。但是為什么這種看似奇怪的方法能得出正確的結(jié)果呢？（以后有時(shí)間再把坑填上~）
最終代碼如下：
#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; } }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
