首页 > 代码库 > 11054 - Wine trading in Gergovia
11054 - Wine trading in Gergovia
题目:11054 - Wine trading in Gergovia
题目大意:每个房子的主人要么买酒,要么卖酒,买和卖的酒的数量一致。卖酒的人需要将酒运送到买酒的人的家里,每将一瓶酒运到相邻的房子就需要耗费一单元的费用,问怎样能使得整体的运送费用最少。
解题思路:不论是卖和买,都需要运送。这样就可以从第一家开始把他手上拥有的酒,或是他想要的酒转移到相邻的那一家。如果刚好一个卖酒一个买酒的话,另一家的需求数量就会减少,反之,如果都是卖,或者都是买,另一家的需求数量酒会增加。这样第一家之后就可以不用考虑了,因为他已将酒买卖全权交给隔壁那一家了。这样往后,最后一家的需求一定是0,因为卖酒买酒总数是固定的。
代码:
#include <stdio.h> #include <stdlib.h> const int N = 100005; long long wines[N]; int main () { int n; while (scanf ("%d", &n), n) { for (int i = 0; i < n; i++) { scanf ("%lld", &wines[i]); } long long count = labs(wines[0]); for (int i = 1; i < n; i++) { wines[i] += wines[i - 1]; count += labs(wines[i]); } printf ("%lld\n", count); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。