UVa 11054 - Wine trading in Gergovia

【链接】

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

【原题】

As you may know from the comic "Asterix and the Chieftain's Shield", Gergovia consists of one street, and every inhabitant of the city is a wine salesman. You wonder how this economy works? Simple enough: everyone buys wine from other inhabitants of the city. Every day each inhabitant decides how much wine he wants to buy or sell. Interestingly, demand and supply is always the same, so that each inhabitant gets what he wants.

There is one problem, however: Transporting wine from one house to another results in work. Since all wines are equally good, the inhabitants of Gergovia don't care which persons they are doing trade with, they are only interested in selling or buying a specific amount of wine. They are clever enough to figure out a way of trading so that the overall amount of work needed for transports is minimized.

In this problem you are asked to reconstruct the trading during one day in Gergovia. For simplicity we will assume that the houses are built along a straight line with equal distance between adjacent houses. Transporting one bottle of wine from one house to an adjacent house results in one unit of work.

Input Specification

The input consists of several test cases. Each test case starts with the number of inhabitantsn(2 ≤n≤ 100000). The following line contains n integers a_i(-1000 ≤ a_i≤ 1000). If a_i≥ 0, it means that the inhabitant living in the i^thhouse wants to buy a_ibottles of wine, otherwise if a_i< 0, he wants to sell -a_ibottles of wine. You may assume that the numbers a_isum up to 0.
The last test case is followed by a line containing 0.

Output Specification

For each test case print the minimum amount of work units needed so that every inhabitant has his demand fulfilled. You may assume that this number fits into a signed 64-bit integer (in C/C++ you can use the data type "long long", in JAVA the data type "long").

Sample Input

5
5 -4 1 -3 1
6
-1000 -1000 -1000 1000 1000 1000
0

Sample Output

9
9000

【题目大意】

一条街上住着连续的n户人家，没相邻的两户人相隔一个单位。街上的每户人都需要买一定数量的葡萄酒或者卖掉葡萄酒，保证所有人家买进的总量与卖出的数量一致。每户可以选择与其他任何家交易。但是因为相隔路程不一样，所以需要路费。路费是按照交易量*相隔距离算的。求所有人都交易满足，最小的路费总和是多少。

【分析与总结】

由于路费和距离相关，所以需要让路程越小越好，那么就可以让每人之和相邻的人交易。 不用考虑他们是要买还是要卖。假设a1要买5个，a2要卖2个，那么就让a1向a2买5个，不用管a2有多少，不够可以打欠条，就变成-3了，这时a3就要向a3买3个。如此算下去，只需要从第一个枚举到最后一个便可得到最小的答案。

【代码】

/*
 *  UVa: 11054 - Wine trading in Gergovia 
 *  Result: Accept
 *  Time: 0.044s
 *  Author: D_Double
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int arr[100002];

int main(){
    int n;
    while(scanf("%d",&n) && n){
        for(int i=0; i<n; ++i)
            scanf("%d",&arr[i]);
        long long ans=0;
        for(int i=0; i<n-1; ++i){
            ans += abs(arr[i]);
            arr[i+1] += arr[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)