## UVa 812 - Trade on Verweggistan

Published on 2016-01-22

## 样例输入

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


## 分析

$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$

## 代码

//  Created by Sengxian on 1/22/16.
//  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;

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;
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