牛客网contest#91 A Wasserstein Distance 贪心

题解：

1、线性扫描数组，两个数组相同下标元素不相等的就开始到数组后面去找数据来补。

2、例如a[0]<b[0]，那么就从下标1开始，向后寻找a[i]>b[i]的数据来补齐，注意考虑寻找到的数据差值比较就行了

3、注意输出数据会爆int。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000+10;
int n,a[maxn],b[maxn];

void slove(){
    long long cnt = 0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    for(int i=0;i<n;i++){
        if(a[i] == b[i]) continue;
        if(a[i] < b[i]){
            int j = i + 1,temp = b[i] - a[i];
            while(temp > 0 && j < n) {
                if(a[j] > b[j]){
                    int cat = min(temp,a[j] - b[j]);
                    cnt += cat * (j - i);
                    temp -= cat;
                    a[j] -= cat;
                }
                j++;
            }
        }
        else {
            int j = i + 1,temp = a[i] - b[i];
            while(temp > 0 && j < n) {
                if(b[j] > a[j]){
                    int cat = min(temp,b[j] - a[j]);
                    cnt += cat * (j - i);
                    temp -= cat;
                    a[j] += cat;
                }
                j++;
            }
        }
    }
    cout << cnt << endl;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--) slove();
    return 0;
}