[ccOCT14] DevuLand, Dinosaurs and Laddus

描述 Description

DevuLand is a very strange place. There are n villages in it. Some of the villages are occupied by dinosaurs while the remaining ones by villagers.

You are given the information of DevuLand by an array D of size n. If D[i] is non-negative, it means that there are D[i] villagers in that village.

Otherwise, it means that are -D[i] dinosaurs in that village.

It is also guaranteed that total number of villagers in DevuLand is equal to total number of dinosaurs.

Once dinosaurs got very hungry and started eating villagers. Frightened villagers gathered immediately and met their Sarpanch Deviji. Deviji, being a very daring and negotiable person, met to the head of dinosaurs. Soon both parties called a truce. It was decided that the villagers will provide laddus to the dinosaurs. So everyday, each villager will take exactly one laddu to one of the dinosaurs in such a way that no dinosaur remains hungry (note that this is possible because number of villagers is the same as the number of dinosaurs).

Actually, carrying laddus is a quite a tough job. Villagers have to use a bullock cart for that. It takes one unit of grass a bullock to carry a cart with 1 laddu for 1 kilometre. Laddus used to be very heavy in DevuLand, so a bullock cart can not carry more than one laddu.

It is also given distance between village indexed i and j is |j - i| (the absolute value) kilometres.

Now villagers sat down and found a strategy to feed laddus to dinosaurs so that they need to buy the least amount of grass from the nearby market.

They are not very good in calculations, please find out what is the minimum number of units of grass they need to buy.

输入格式 InputFormat

First line of the input contains an integer T denoting number of test cases.

For each test case, there are two lines.

First line contains a single integer denoting n: number of villages.
Second line contains n space separated integers denoting the array D.

输出格式 OutputFormat

For each test case, print a single line containing the integer corresponding to answer of the problem.

样例输入 SampleInput

3
2
5 -5
2
-5 5
3
1 2 -3

样例输出 SampleOutput

5
5
4

CodeChef PRLADDU

代码 Code

因为村庄都位于一条数轴上，所以尽可能从近的村民处往恐龙村送切糕即可。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
//int a[100005],b[100005];
vector < pair<int,int> > va,vc;
int T;
long long ans;
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        va.clear();
        vc.clear();
        scanf("%d",&n);
        l=r=0;
        for (i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if (x==0) continue;
            if (x>0) va.push_back(make_pair(i,x));
            else vc.push_back(make_pair(i,-x));
        }
        ans=0;
        for (l=0,i=0;i<vc.size();) 
        {
            t=min(vc[i].second,va[l].second);
            ans+=abs(vc[i].first-va[l].first)*t;
            vc[i].second-=t;
            va[l].second-=t;
            if (vc[i].second==0) i++;
            if (va[l].second==0) l++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}