UVA 10670 Work Reduction：貪心策略與字串解析最小化外包成本

題目大意

老板給 n 份文件，最終需保留 m 份。有 L 家公司提供服務，每家報價格式：
Name:A,B 其中 A = 單份處理費，B = 整批減半費用（將當前份數減半，但不得低於 m）。
求每家公司完成任務的最小總費用，按費用升序、名稱字典序輸出。

貪心決策邏輯

當前剩餘 cur 份文件：

• 若 cur/2 ≥ m 且 (cur - cur/2)*A ≥ B（減半比逐份處理划算）→ 選擇減半，費用 +B，cur /= 2。
• 否則 → 直接逐份處理至 m，費用 +(cur - m)*A，結束。

證明：減半操作越早做單價越劃算，且費用固定，滿足條件時貪心選擇最優。

字串解析關鍵

輸入行格式：CompanyName:123,456。需分離名稱、A、B。
掃描到 : 前為名稱，: 後第一個 , 前為 A，之後為 B。

完整代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 105;
struct Company {
    char name[N];
    int money, a, b;
} com[N];

char str[N];

bool cmp(const Company& x, const Company& y) {
    if (x.money != y.money) return x.money < y.money;
    return strcmp(x.name, y.name) < 0;
}

void parse(int idx) {
    int i = 0;
    while (str[i] != ':') i++;
    strncpy(com[idx].name, str, i);
    com[idx].name[i] = '\0';

    int sum = 0;
    for (int j = i+1; str[j]; j++) {
        if (str[j] != ',') sum = sum*10 + str[j]-'0';
        else { com[idx].a = sum; sum = 0; }
    }
    com[idx].b = sum;
}

void calc(int idx) {
    int cur = ::n, cost = 0;
    while (1) {
        if (cur/2 >= m && (cur - cur/2)*com[idx].a >= com[idx].b) {
            cost += com[idx].b;
            cur /= 2;
        } else {
            cost += (cur - m) * com[idx].a;
            break;
        }
    }
    com[idx].money = cost;
}

int n, m, l;

int main() {
    int T; scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        char ch; scanf("%d%d%d%c", &n, &m, &l, &ch);
        for (int i = 0; i < l; i++) {
            gets(str);
            parse(i);
            calc(i);
        }
        sort(com, com+l, cmp);
        printf("Case %d\n", tc);
        for (int i = 0; i < l; i++)
            printf("%s %d\n", com[i].name, com[i].money);
    }
    return 0;
}

注意事項

• gets 讀整行含空格，前一個 scanf 需吃掉換行符（用 %c 讀取）。
• 減半條件嚴格：cur/2 >= m 且 減半省下的錢 ≥ B。
• 排序先按費用，再按名稱字典序（strcmp）。