uva 11054——Wine trading in Gergovia

约定不等于承诺〃 2022-08-10 00:48 23阅读 0赞

题意：有n个村庄，每个村庄要么买酒（+），要么卖酒（-），要求供需平衡，求最小代价（代价k为把k个单位的酒运到相邻的村庄）。

思路：贪心。可以把第1个村庄的所有酒都从第2个村庄运来，那么12可以合二为一，其他村庄需要运a+b的酒到12村庄，依次类推。

code：

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <sstream>
    #include <string>
    #include <vector>
    #include <list>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    
    const int INF=0x3fffffff;
    const int inf=-INF;
    const int N=1000000;
    const int M=2005;
    const int mod=1000000007;
    const double pi=acos(-1.0);
    
    #define cls(x,c) memset(x,c,sizeof(x))
    #define cpy(x,a) memcpy(x,a,sizeof(a))
    #define fr(i,s,n) for (int i=s;i<=n;i++)
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define lrt  rt<<1
    #define rrt  rt<<1|1
    #define middle int m=(r+l)>>1
    #define lowbit(x) (x&-x)
    #define pii pair<int,int>
    #define mk make_pair
    #define IN freopen("in.txt","r",stdin);
    #define OUT freopen("out.txt","w",stdout);
    
    int main()
    {
        int n;
        while (~scanf("%d",&n),n)
        {
            ll ans=0,a,la=0;
            fr(i,1,n)
            {
                cin>>a;
                ans+=abs(la);
                la+=a;
            }
            printf("%lld\n",ans);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，23人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 11504--Wine trading in Gergovia（思维题）

题意：把k个单位的酒从村庄运到相邻村庄需要k个单位的劳动力。计算最少需要多少劳动力可以满足所有村庄的需求。输出保证在64为带符号整数的范围内。紫书上的思路:考虑最左边的村

灰太狼/ 2024年02月17日 22:44/ 0 赞/ 38 阅读

相关 Wine（ubuntu）

Wine 1 简介 2 安装 & 卸载 2.1 安装 2.2 卸载 3 wine命令参考 1 简介 Wine

偏执的太偏执、/ 2022年11月07日 11:43/ 0 赞/ 268 阅读

相关 Wine笔记

虚拟机是模拟CPU； Wine是API转化，将Winsows API转化为Linux API。例如，Win下打开文件的API是`CreateFile( )`，Linux下打

你的名字/ 2022年10月28日 15:21/ 0 赞/ 1244 阅读

相关 FatMouse' Trade

FatMouse' Trade Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 FatMou

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 05:59/ 0 赞/ 166 阅读

相关 uva 11054——Wine trading in Gergovia

题意：有n个村庄，每个村庄要么买酒（+），要么卖酒（-），要求供需平衡，求最小代价（代价k为把k个单位的酒运到相邻的村庄）。思路：贪心。可以把第1个村庄的所有酒都

约定不等于承诺〃/ 2022年08月10日 00:48/ 0 赞/ 24 阅读

相关 ACM 扫描法 Wine trading in Gergovia

滴，集训第七天打卡。今天是紫书第八章训练，是高效算法设计.. 就是不用奇技淫巧都会超时... 这里贴一题扫描法。 UVA 11054 Wine tradin

柔情只为你懂/ 2022年06月12日 12:45/ 0 赞/ 87 阅读

相关 wine

sudo apt-get install wine root@sharps-computer:/opt/java sudo apt-get install wine

Love The Way You Lie/ 2022年05月12日 07:30/ 0 赞/ 321 阅读

相关 FatMouse’ Trade

简介贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法

╰半橙微兮°/ 2022年04月24日 06:20/ 0 赞/ 194 阅读

相关 ACM — FatMouse' Trade

Link [http://acm.hdu.edu.cn/showpro...][http_acm.hdu.edu.cn_showpro...] Problem Des

你的名字/ 2022年02月20日 14:51/ 0 赞/ 261 阅读

相关 FatMouse' Trade

题目连接：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40692\problem/A][http_acm.hu

「爱情、让人受尽委屈。」/ 2021年06月24日 13:58/ 0 赞/ 236 阅读