By yusijia

Updated:

Contents
  1. 1. 等价转换
  2. 2. 题目大意：
    1. 2.1. 分析：

白皮书训练：

UVa11054，poj2940

等价转换

题目大意：

　　一条街上有很多葡萄酒店，正数代表要运走，负数代表要运进。总和是０；
然后就是怎么全部运成０，每一个单位的酒运到隔壁要一个单位钱(劳动力)，问钱最少多少。

分析：

　　考虑最左边的村庄，因为最后是平衡的，所以如果需要买酒则一定有劳动力从右边的村庄往左边运，卖酒也是一样的。
这样,问题就等价于只有村庄A(1)和村庄B(2~n),然后村庄A(1~n-1)，村庄B(n)，最后只需要求出左边的村庄A的需求就可以了，
这里也使用到了一个贪心策略：找最小的距离，距离都为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

int main()
{
    int n;
    while(scanf("%d", &n) != EOF && n){
        long long sum = 0, a, last = 0;
        for(int i = 0; i < n; i++){
            scanf("%I64d", &a);
            sum += abs(last);
            last += a;
        }
        printf("%I64d\n", sum);
    }
    return 0;
}
Contents
  1. 1. 等价转换
  2. 2. 题目大意：
    1. 2.1. 分析：