首页 > 代码库 > UVa 11054 Gergovia的酒交易
UVa 11054 Gergovia的酒交易
https://vjudge.net/problem/UVA-11054
题意：直线上有n个等距的村庄，每个村庄要么买酒，要么卖酒。设第i个村庄对酒的需求为ai，ai>0表示买酒，ai<0表示卖酒，所有村庄供需平衡。把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力。计算所需最少劳动力。
思路：从左边第一个开始分析，如果它卖酒，则可以把它全卖给第二个村庄，如果它买酒，可以从第二个村庄那里买酒，依次下去分析第二个直到最后一个村庄。这样的话每次买酒和卖酒的距离都是最短的，劳动力肯定也是最少的。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 100000 + 5; 7 8 int n; 9 int ans[maxn];10 long long k;11 12 int main()13 {14 //freopen("D:\\txt.txt", "r", stdin);15 while (cin >> n && n)16 {17 for (int i = 0; i < n; i++)18 cin >> ans[i];19 k = 0;20 for (int i = 0; i < n - 1; i++)21 {22 ans[i + 1] = ans[i + 1] + ans[i];23 k += abs(ans[i]);24 }25 cout << k << endl;26 }27 28 return 0;29 }
UVa 11054 Gergovia的酒交易
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。