CodeVS/1098

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
均分纸牌	★☆☆☆☆	答案正确	100	2014-10-11 16:37:59	看漏条件（40）

题意

每叠纸牌向左移或者向右移若干张算是一次移动，求使所有纸牌相等最少移动步数。

题解

第一次居然把题目看漏了也是醉了，没看到只能移动到相邻的塔上，居然还有分过样例也是醉了。既然写了也蛮贴出来，是一个O（logn）的算法。

不限定相邻.cpp代码已折叠 展开折叠内容
#include<iostream> #include<algorithm> int p[101],n,average=0,count=0; int main() { std::cin>>n; for(int i=1;i<=n;++i) { std::cin>>p[i]; average+=p[i]; } average/=n; for(int i=1;i<=n;++i) p[i]-=average; std::sort(p+1,p+n+1); while(p[1]) { if(p[n]<=-p[1]) { p[1]+=p[n]; p[n]=0; } else { p[n]+=p[1]; p[1]=0; } ++count; std::sort(p+1,p+n+1); } std::cout<<count; return 0; }

然后我们回到这题。一开始愣了很久，想不出来度娘看了两行就恍然原来做过。也是很神奇很经典的一个贪心啦。 首先先计算一下平均值，也就是最后目标每一堆要放多少，然后计算出每一堆要多还少补多少。 然后就开始移动了，明显每一堆不满足要求的都要移动，不如就从左往右开始，原因是最左边一堆只有一个来源/去路，所以很适合做开始的点。 最左边一堆无论多少只能通过右边的拿或者放，于是一次性补齐了就好。当然也可能出现右边东西不够补，但是早晚也要补，补的时间可以改变是等效的，但总是要补的，为了最优解当然要一次性补完，因此补成负数也没有关系。 右边以此类推，最左边的补齐了，就当做其不存在，直接循环下去就好了。

代码

1098.cpp代码已折叠 展开折叠内容
#include<iostream> int p[101],n,average=0,count=0; int main() { std::cin>>n; for(int i=1;i<=n;++i) { std::cin>>p[i]; average+=p[i]; } average/=n; for(int i=1;i<=n;++i) p[i]-=average; for(int i=1;i<=n;++i) if(p[i]) { p[i+1]+=p[i]; ++count; } std::cout<<count<<std::endl; return 0; }