UVa 812 - Trade on Verweggistan

#贪心 #优先队列 #多路归并问题

Published on 2016-01-22

描述

有一种物品真实价值是 $10$ 个单位，现在有 $n(n\le 50)$ 堆该物品，每一堆有 $m_i(0\le m_i\le20)$ 件该物品，而每一堆每件该物品的售价不同。为了买到某一堆的某个物品，你必须将这一堆这一物品上面的物品全部购买。问你最多能得到多少利润，以及达到该利润至少需要买多少物品（可能有多解，如果大于 $10$ 个，仅输出最小的 $10$ 个）。

样例输入

1
6 12 3 10 7 16 5
2
5 7 3 11 9 10
9 1 2 3 4 10 16 10 4 16
0

样例输出

Workyards 1
Maximum profit is 8.
Number of pruls to buy: 4

Workyards 2
Maximum profit is 40.
Number of pruls to buy: 6 7 8 9 10 12 13

分析

首先只考虑获得最大的利润。对于每一堆物品，我们用成本去减这一堆每一件物品的售价以得到利润，再求一个前缀和，位置 $i$ 的前缀和就代表买到位置 $i$ ，所能获得的利润。那么最大的前缀和就是这一堆物品能得到的最大获利。总的最大利润就是每一堆的最大获利之和（当然不要负数）。举个例子，看这样一堆物品（左边为堆顶）：

13, 7, 5, 14, 8, 17, 6, 5 \longrightarrow -3, 3, 4, -4, 2,-7, 4, 5

求取前缀和：

-3, 0, 4, 0, 2,-5, -1, 4

可以看出来，买到第 $3$ 或者第 $8$ 个物品得利最大，为 $4$ 个单位。
好，现在最大利润已经搞定了，那么如何求买多少可以得到最大利润呢？由于每一堆里面可买的有可能不唯一（例如上面的例子，买 $3$ 个或者 $8$ 个物品都可以），所以这个问题就变成：
每一堆里面有多个可以选取的数（结果为负数的堆不参加），在每一堆里面选取一个数，求最小且不同的 $10$ 个和，这正是多路归并问题，在 UVa 11997 - K Smallest Sums 有详细介绍，这里不再重复。
有一点不同的是，如果某一堆的最大获利是 $0$ ，那么不仅要添加所有前缀和为 $0$ 的位置的购买个数，而且要添加购买 $0$ 件商品，毕竟可以不在这一堆买。
最后如果不能在任何一堆买，特判输出 $0$ 。
本题细节较多，详见代码。

代码

//  Created by Sengxian on 1/22/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 812 贪心 + 多路归并
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n')
using namespace std;
const int maxn = 50 + 3, maxm = 20 + 3, maxk = 10;
vector<int> a[maxn];
int t[maxm], cnt, n;

inline int ReadInt() {
    int x = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    do {
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(isdigit(ch));
    return x;
}

typedef pair<int, int> state;
void merge(vector<int> &a, vector<int> &b) {
    priority_queue<state, vector<state>, greater<state> > pq;
    for(int i = 0; i < a.size(); ++i) pq.push(state(a[i] + b[0], 0));
    a.clear();
    for(int i = 0; a.size() < maxk && !pq.empty(); ++i) {
        state now = pq.top(); pq.pop();
        int idx = lower_bound(a.begin(), a.end(), now.first) - a.begin();
        if(idx < 0 || idx >= a.size() || a[idx] != now.first) a.push_back(now.first);
        if(now.second + 1 < b.size()) pq.push(state(now.first - b[now.second] + b[now.second + 1], now.second + 1));
    }
}

int main() {
    int caseNum = 0;
    while(n = ReadInt(), n) {
        if(caseNum) br;
        printf("Workyards %d\n", ++caseNum);
        cnt = 0; int profit = 0;
        a[0].clear(); //important!
        for (int i = 0; i < n; ++i) {
            int b = ReadInt(), Max = 0;
            if(!b) continue;
            for(int j = 0; j < b; ++j) t[j] = 10 - ReadInt();
            for(int j = 0; j < b - 1; ++j) t[j + 1] += t[j];
            Max = *max_element(t, t + b);
            if(Max >= 0) {
                profit += Max;
                a[cnt].clear();
                if(Max == 0) a[cnt].push_back(0);
                for(int j = 0; j < b; ++j) if(t[j] == Max) a[cnt].push_back(j + 1);
                cnt++;
            }            
        }
        n = cnt;
        printf("Maximum profit is %d.\nNumber of pruls to buy:", profit);
        for(int i = 1; i < n; ++i) merge(a[0], a[i]);
        for(int i = 0; i < a[0].size() && i < 10; ++i) printf(" %d", a[0][i]);
        if(a[0].size() == 0) printf(" 0");
        br;
    }
    return 0;
}

附加输入

9
19 18 13 8 1 8 6 16 13 6 8 17 5 18 5 3 5 4 12 1
2 7 12
8 4 12 8 7 1 15 5 10
9 9 17 4 8 15 20 12 20 7
0
2 5 5
1 1
0
18 13 4 8 16 12 3 7 19 1 7 5 6 9 9 6 17 12 6
1
14 17 10 10 5 6 6 1 4 18 1 5 10 16 5
5
5 19 3 17 20 9
5 17 9 10 2 6
2 7 16
17 16 18 17 12 3 14 13 18 11 5 2 12 20 18 8 6 17
18 2 8 10 15 4 19 16 17 4 1 16 11 8 11 8 4 2 2
7
0
6 19 10 13 10 9 10
17 6 18 6 20 17 7 14 12 5 2 9 20 2 16 11 9 6
5 12 19 4 20 5
10 18 6 14 19 15 16 15 12 5 12
10 14 18 5 5 15 18 13 6 19 20
9 7 17 18 10 16 1 1 12 14
10
8 20 8 3 7 14 7 11 17
18 16 6 13 1 20 10 5 6 8 5 13 6 1 2 15 16 14 7
18 8 16 8 7 3 2 13 8 8 15 4 17 11 10 9 3 1 19
8 18 6 11 3 12 12 4 18
14 10 17 10 17 12 9 15 7 10 7 14 10 13 10
16 15 11 14 17 11 12 16 1 10 6 3 13 9 18 2 20
15 18 9 3 10 17 17 8 18 15 13 19 20 2 4 14
5 10 3 3 13 18
6 14 3 17 6 4 14
19 3 1 17 11 15 18 19 12 5 16 18 18 7 17 19 10 11 3 11
5
13 16 2 19 9 16 7 15 19 20 14 1 12 10
1 7
2 13 10
3 1 7 1
19 16 12 8 18 14 19 2 10 14 3 20 2 18 18 8 17 17 1 9
1
17 12 19 2 4 8 5 16 6 18 2 1 1 10 18 6 8 19
7
8 1 18 6 11 15 14 7 3
3 7 3 20
0
17 1 14 20 18 9 6 7 3 18 7 12 16 4 11 6 10 15
18 7 20 9 1 5 7 15 3 13 18 2 3 10 3 8 10 12 8
2 18 10
1 4
3
19 7 3 17 8 17 15 14 9 15 6 13 13 20 7 5 9 9 19 19
6 18 8 14 18 14 11
7 17 6 12 16 4 6 4
1
20 18 16 3 4 1 7 16 12 14 20 1 14 11 11 16 20 18 9 17 3
2
0
1 10
1
0
0

附加输出

Workyards 1
Maximum profit is 90.
Number of pruls to buy: 47 49 50

Workyards 2
Maximum profit is 27.
Number of pruls to buy: 11 12

Workyards 3
Maximum profit is 31.
Number of pruls to buy: 24

Workyards 4
Maximum profit is 7.
Number of pruls to buy: 2

Workyards 5
Maximum profit is 97.
Number of pruls to buy: 52 53 55 56 57

Workyards 6
Maximum profit is 26.
Number of pruls to buy: 6

Workyards 7
Maximum profit is 26.
Number of pruls to buy: 12 13

Workyards 8
Maximum profit is 60.
Number of pruls to buy: 20 21 23

Workyards 9
Maximum profit is 15.
Number of pruls to buy: 9

Workyards 10
Maximum profit is 11.
Number of pruls to buy: 6

Workyards 11
Maximum profit is 0.
Number of pruls to buy: 0 1

Workyards 12
Maximum profit is 0.
Number of pruls to buy: 0

UVa 1382 - Distant Galaxy UVa 1533 - Moving Pegs

Sengxian's Blog