UVa 10670 - Work Reduction

链接

传送门

题意

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

思路

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

代码

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