（以“分类:贪心 ==摘要== {{信息题|均分纸牌|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}} | ||
然后我们回到这题。一开始愣了很久，想不出来度娘看了两行就恍然原来做过。也是很神奇很经典的一个贪心啦。 | 然后我们回到这题。一开始愣了很久，想不出来度娘看了两行就恍然原来做过。也是很神奇很经典的一个贪心啦。 | ||
首先先计算一下平均值，也就是最后目标每一堆要放多少，然后计算出每一堆要多还少补多少。 | 首先先计算一下平均值，也就是最后目标每一堆要放多少，然后计算出每一堆要多还少补多少。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 均分纸牌 | ★☆☆☆☆ | 答案正确 | 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;
}
|
CloudLunar