UVa 11054 - Wine trading in Gergovia

2021-07-19 16:25

阅读：1010

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1995

题意：

直线上有n（2≤n≤100000）个等距的村庄，每个村庄要么买酒，要么卖酒。
设第i个村庄对酒的需求为ai（-1000≤ai≤1000），其中ai>0表示买酒，ai
把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力。
计算最少需要多少劳动力可以满足所有村庄的需求。输出保证在64位带符号整数的范围内。

分析：

问题等价转换。
考虑最左边的村庄。如果需要买酒，即a1>0，则一定有劳动力从村庄2往左运给村庄1，
而不管这些酒是从哪里来的（可能就是村庄2产的，也可能是更右边的村庄运到村庄2的）。
这样，问题就等价于只有村庄2～n，且第2个村庄的需求为a1+a2的情形。
不难发现，ai

代码：

 1 #include  2 #include  3 
 4 int main(){
 5     int n;
 6     while(scanf("%d", &n) && n){
 7         int need;
 8         scanf("%d", &need);
 9         long long last = need, ans = abs(need);
10         for(int i = 1; i ){
11             scanf("%d", &need);
12             last += need;
13             ans += abs(last);
14         }
15         printf("%lld\n", ans);
16     }
17     return 0;
18 }

上一篇：Spark 学习笔记之 Streaming Window

下一篇：基于Abp的WebApi容器

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：UVa 11054 - Wine trading in Gergovia
文章链接：http://soscw.com/index.php/essay/106344.html

亲，登录后才可以留言！

UVa 11054 - Wine trading in Gergovia

评论

热门文章

推荐文章

最新文章

置顶文章