(以“分类:贪心 ==摘要== {{信息题|均分纸牌|http://www.codevs.cn/problem/1098/|1|100|看漏条件|40|time=2014-10-11 16:37:59}} ==题意== 每叠纸牌向...”为内容创建页面)
 
(第一段代码与描述不符)
 
第40行: 第40行:
 
     std::cout<<count;
 
     std::cout<<count;
 
     return 0;
 
     return 0;
}</pre>|code01}}
+
}
 +
</pre>|code01}}
 
然后我们回到这题。一开始愣了很久,想不出来度娘看了两行就恍然原来做过。也是很神奇很经典的一个贪心啦。
 
然后我们回到这题。一开始愣了很久,想不出来度娘看了两行就恍然原来做过。也是很神奇很经典的一个贪心啦。
 
首先先计算一下平均值,也就是最后目标每一堆要放多少,然后计算出每一堆要多还少补多少。
 
首先先计算一下平均值,也就是最后目标每一堆要放多少,然后计算出每一堆要多还少补多少。

2014年10月11日 (六) 16:36的最后版本

摘要

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

题意

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

题解

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

不限定相邻.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;
}

著作权声明[编辑]

关于[编辑]