uva11054 - Wine trading in Gergovia（等价转换，贪心法）

2020-12-13 13:41

阅读：344

标签：style blog color io os for sp div on

这个题看上去麻烦，实际上只要想清楚就很简单。关键是要有一种等价转换的思维方式。其实题意就是个一排数，最后通过相邻的互相移动加减使得所有数都变成零，移动过程中每次都耗费相应值，让耗费的值最小。虽然从实际看来只能从负的移给正的，但实际结果谁给谁消耗的都一样。

有了这些等价思考，就可以用贪心法做了：第一个数要想变成0，那么必须和第二个数相互移，那么不管谁移给谁，消耗的就是第一个数的绝对值，最后第一个数变0，第二个数变a[1]+a[2]了。这样第2至n个数还是这样的思考方式。这种做法的每一步的消耗都是必不可少的，如果这这样的结果还小，那就不可能每个数都变成0了，所以这么贪心出来的结果是最优解。

#include
#include
#include
#include
#include
#include
#includeset>
#include
#include
#include
#include
#include
#includeusing namespace std;
#define INF 1000000000
#define eps 1e-8
#define pii pair#define LL long long int
#define maxn 100000+10
int n,a;
LL ans=0,t=0;
int main()
{
    //freopen("in8.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d",&n)==1&&n)
    {
        ans=0;
        t=0;
        for(int i=0;i)
        {
            scanf("%d",&a);
            t+=a;
            ans+=abs(t);
        }
        printf("%lld\n",ans);
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

uva11054 - Wine trading in Gergovia（等价转换，贪心法）

标签：style blog color io os for sp div on

原文地址：http://www.cnblogs.com/zywscq/p/4053286.html

上一篇：Studying TCP's Congestion Window using NS

下一篇：Java自学-继承与接口 Object类

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：uva11054 - Wine trading in Gergovia（等价转换，贪心法）
文章链接：http://soscw.com/essay/33182.html

亲，登录后才可以留言！

uva11054 - Wine trading in Gergovia（等价转换，贪心法）

评论

热门文章

推荐文章

最新文章

置顶文章