一、题意

直线上有n个等距的村庄（n<=100000），每个村庄要么买酒，要么卖酒。
设第i个村庄的需求为ai，ai>0表示买酒，ai<0表示卖酒，sum(ai)=0。
若把x数量的就从一个村庄运到隔壁村庄需要x人力，
求总共需要多少人力完成所有买卖。

二、解析

这是一道很有意思的题目。首先我们可以认为，把x数量的酒从b运到a 等价于 把-x数量的酒从a运到b，他们的花费都是abs(x)。这是什么意思呢？就是说，不要死脑筋的想着运输方向的问题，我们完全可以把所有的运酒过程表述为一个方向的，只不过反方向的我们用负来表示而已。

这样我们就只需要从直线的左端走到右端就可以了，维护一个cur表示当前你身上放了多少酒（可以为负，表示你还没到的村庄将会往你这里运多少酒，这里我们表述为你需要运负这么多酒到接下来的村庄），然后你每往前走一个村庄，你就必须缴纳相应的人力费用（即abs(cur)，若cur<0，则可以理解为缴纳从接下来的村庄运酒到你这里的费用），把费用累加到ans中即可。

三、代码

#include <iostream>
#include <cmath>
using namespace std;
using LL = long long;
int n;

int main() {
    while(cin >> n && n) {
        LL cur = 0, ans = 0;
        for(int i = 0, x; i < n; i ++) {
            cin >> x;
            cur -= x;
            ans += abs(cur);
        }
        cout << ans << endl;
    }
}

四、归纳

  • 思考10分钟，代码1分钟。做题果然还是要想清楚（包括正确性、时间复杂度）再下手，不然写出的代码都是无用功。

想当年再leetcode有刷过类似的题...然后硬是想不通2333