查看CodeVS/1098的源代码 ←CodeVS/1098

[[分类:贪心]]
==摘要==
{{信息题|均分纸牌|http://www.codevs.cn/problem/1098/|1|100|看漏条件|40|time=2014-10-11 16:37:59}}
==题意==
每叠纸牌向左移或者向右移若干张算是一次移动，求使所有纸牌相等最少移动步数。
==题解==
第一次居然把题目看漏了也是醉了，没看到只能移动到相邻的塔上，居然还有分过样例也是醉了。既然写了也蛮贴出来，是一个O（<m>n^2</m>logn）的算法。
{{折叠|不限定相邻.cpp代码已折叠|
<pre>
#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;
}</pre>|code01}}
然后我们回到这题。一开始愣了很久，想不出来度娘看了两行就恍然原来做过。也是很神奇很经典的一个贪心啦。
首先先计算一下平均值，也就是最后目标每一堆要放多少，然后计算出每一堆要多还少补多少。
然后就开始移动了，明显每一堆不满足要求的都要移动，不如就从左往右开始，原因是最左边一堆只有一个来源/去路，所以很适合做开始的点。
最左边一堆无论多少只能通过右边的拿或者放，于是一次性补齐了就好。当然也可能出现右边东西不够补，但是早晚也要补，补的时间可以改变是等效的，但总是要补的，为了最优解当然要一次性补完，因此补成负数也没有关系。
右边以此类推，最左边的补齐了，就当做其不存在，直接循环下去就好了。
==代码==
{{折叠|1098.cpp代码已折叠
|<pre>#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;
}
</pre>
|code1098}}