UVa 11054 - Wine trading in Gergovia

#贪心 #思维 #模拟
Published on 2016-02-03

题目地址

描述

直线上有 n(n≤100000)n(n\le100000) 个距离为 11 个单位的村庄，从左到右依次排列。每个村庄要么要买酒，要么要卖酒，具体的数量用 ai(−1000≤ai≤1000)a_i(-1000\le a_i \le 1000) 表示（ai>0a_i > 0 表示买酒，ai<0a_i < 0 表示卖酒）。把 kk 个单位的酒运送 11 个单位的距离需要 kk 个单位的劳动力，问你最少需要多少劳动力才能够满足所有酒庄的需求？

样例输入

5
5 -4 1 -3 1
6
-1000 -1000 -1000 1000 1000 1000
0

样例输出

9
9000

分析

首先可以知道，一个村庄要买酒/卖酒，肯定是要就近操作才优。其次，某一个村庄买酒，那么一定有村庄卖酒，这个过程是相互的，所以先处理谁都不影响。那么就可以脑补出一个贪心算法。
从左到右依次处理每个酒庄，如果要买酒，那么就从它右边要卖酒的村庄从近到远依次买酒（左边酒庄已经处理平衡了）。反之亦然。我们用队列模拟买酒和卖酒的村庄，由于元素进队和出队的次数都是 11 次，复杂度是 O(n)O(n) 的。

代码

//  Created by Sengxian on 2/3/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 11054 贪心, 模拟, 思维
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n')
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar(); bool flag = false;
    while(ch < '0' || ch > '9') {
        if(ch == '-') flag = true;
        ch = getchar();
    }
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return flag ? -n : n;
}

typedef long long ll;
const int maxn = 100000 + 3;
int a[maxn], pos[maxn], ep, p, neg[maxn], eq, q, n;

ll Solve() {
    ll ans = 0;
    p = q = 0;
    for(int i = 0; i < n; ++i) {
        if(a[i] == 0) continue;
        else if(a[i] > 0) {
            while(a[i]) { //从近到远找负的酒馆
                if(a[neg[q]] == 0) q++;
                if(a[i] >= abs(a[neg[q]])) {
                    a[i] += a[neg[q]];
                    ans += (ll)(neg[q] - i) * abs(a[neg[q]]);
                    a[neg[q++]] = 0;
                }else {
                    a[neg[q]] += a[i];
                    ans += (ll)(neg[q] - i) * a[i];
                    a[i] = 0;
                }
            }
        }else {
            while(a[i]) { //从近到远找正的酒馆
                if(a[pos[p]] == 0) p++;
                if(abs(a[i]) >= a[pos[p]]) {
                    a[i] += a[pos[p]];
                    ans += (ll)(pos[p] - i) * a[pos[p]];
                    a[pos[p++]] = 0;
                }else {
                    a[pos[p]] += a[i];
                    ans += (ll)(pos[p] - i) * abs(a[i]);
                    a[i] = 0;
                }
            }
        }
    }
    return ans;
}

int main() {
    while(n = ReadInt(), n) {
        ep = eq = 0;
        for(int i = 0; i < n; ++i) {
            a[i] = ReadInt();
            if(a[i] > 0) pos[ep++] = i; //记录正的位置
            else if(a[i] < 0) neg[eq++] = i; //记录负的位置
        }
        printf("%lld\n", Solve());
    }
    return 0;
}

附加输入

10
100 200 300 400 500 -500 -400 -300 -200 -100
10
100 200 300 400 500 -100 -200 -300 -400 -500
10
100 -100 200 -200 300 -300 400 -400 500 -500
3
-10 20 -10
10
100 200 300 400 500 600 700 800 900 -4500
10
-2100 500 400 300 200 500 800 400 600 -1600
15
-1 -2 -3 -4 5 -6 7 -8 9 -10 11 -12 13 -14 15
0

附加输出

5500
7500
1500
20
16500
9900
100
UVa 1312 - Cricket Field