学步园

贪心，本来想的贪心方法是找到每一个需求量为正数的居民，往两边搜，搜到最近的那个需求量为负的居民，权衡需求量与销售量不难最少使其中的一个变为零，另外一个如果不为零，则减去或加上另一个的需求量，不断重复操作，直到所有居民的数值均为零。虽然后来中间也做了不少剪枝，但最后还是TLE了。

后来参考了http://hi.baidu.com/knowledgetime/blog/item/fbcfe9c9b6ad4048f21fe7d1.html的贪心方法，觉得这个方法非常巧妙，可以将其看成每次只有邻居间互相买卖葡萄酒，最后统计总的出入金额便可。

代码如下：

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

int a[100002];
int main()
{
#ifdef test
    freopen("in.txt", "r", stdin);
#endif
    int num;
    while(scanf("%d", &num), num)
    {
        long long sum = 0, fm = 0;
        for(int i = 0; i < num; i++)
            scanf("%d", &a[i]);
        for(int i = 0; i < num; i++)
        {
            sum += abs(fm);
            fm += a[i];
        }
        printf("%lld\n", sum);
    }
    return 0;
}