UVa 10670 - Work Reduction

链接

传送门

题意

给出\(n\)个工作,但你只需要自己做\(m\)个,其他的找代理做,有\(l\)个代理,每个代理的收费不同,但都包含两项:1、收费\(A\),完成一项工作;2、收费\(B\),完成一半的工作(向上取整)。输出对所有代理收费排序后的序列。

思路

对每个代理,优先使用第二种方案,求出花费,然后排序。数据读入上,使用类正则表达式更加方便。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 110;
struct agency{
char s[110];
int c;
bool operator < (const agency& rhs) const {
return c < rhs.c || (c == rhs.c && strcmp(s, rhs.s) < 0);
}
} a[maxn];

int main() {
int t, tt = 0;
scanf("%d", &t);
while (t--) {
int n, m, l;
scanf("%d%d%d\n", &n, &m, &l);
for (int i = 0; i < l; ++i) {
int A, B, num = n;
scanf("%[^:]:%d,%d\n", a[i].s, &A, &B);
a[i].c = 0;
while ((num >> 1) >= m && A * (num >> 1) > B) {
num /= 2;
a[i].c += B;
}
a[i].c += (num - m) * A;
}
sort(a, a + l);
printf("Case %d\n", ++tt);
for (int i = 0; i < l; ++i) {
printf("%s %d\n", a[i].s, a[i].c);
}
}
return 0;
}