Poj 3040: Allowance

題目

分析

果然驗證了「過早的優化是萬惡之源」──我手賤地在一個地方優化，但那個優化完全想錯了──於是 WA 到快瘋掉。

參考 http://www.hankcs.com/program/cpp/poj-3040-allowance.html

想法是這樣：

從原始的找零錢問題可得知：如果可以組出 C 元，那使用 先大後小 的策略是正確的。
但這題要組出 大於或等於 C 元，我們可以採取用 (1) 的方法組出 K 元，K <= C 且 K 愈接近 C 愈好。
如果 K ≠ C，那之後再 從小到大 地找一個硬幣加上去，使得價值大於等於 C。
(3) 保證有效是因為 (2) 保證了 C - K 比最小硬幣的價值還小。這時既然要再加一個硬幣進去才能大於等於 C，且不管放哪種價值的都可以，那當然是從價值小的開始放。
在最一開始，如果某種硬幣的價值已經大於等於 C，那當然這種硬幣一個就可以用一個星期，這在程式的一開始就先處理掉。
實作時，不能一個星期一個星期試可不可以組出來，這樣會 TLE，得變成：不斷地找一種組法，看這種組法能用幾個星期，直到找不到為止。

這題實作也不容易啊。

AC Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>

using namespace std;

struct Coin {
    int value;
    int number;

    bool operator > (const Coin& c) const {
        return value > c.value;
    }
};

int N, C;
Coin coins[20];

int solve() {
    sort(coins, coins + N, greater<Coin>());

    int cnt = 0;
    for (int i = 0; i < N && coins[i].value >= C; i++) {
        cnt += coins[i].number;
        coins[i].number = 0;
    }

    int need[20];
    while (true) {
        // 找到一組可行解
        memset(need, 0, sizeof(need));
        int money = C;

        // 從大到小
        for (int i = 0; i < N; i++) {
            if (coins[i].number <= 0)
                continue;
            if (money <= 0)
                break;

            int used = min(coins[i].number, money / coins[i].value);
            money -= used * coins[i].value;
            need[i] = used;
        }

        // 從小到大
        for (int i = N-1; i >= 0; i--) {
            if (coins[i].number <= 0)
                continue;
            if (money <= 0)
                break;

            int used = min(coins[i].number - need[i], money / coins[i].value + ((money % coins[i].value != 0) ? 1 : 0));
            // int used = min(coins[i].number - need[i], (money + coins[i].value - 1) / coins[i].value);
            money -= used * coins[i].value;
            need[i] += used;
        }

        // 找不到解
        if (money > 0)
            break;

        // 計算這組可行解可以用幾個星期
        int week = 1 << 30;
        for (int i = 0; i < N; i++) {
            if (need[i] == 0)
                continue;
            week = min(week, coins[i].number / need[i]);
        }
        if (week == 0)
            break;
        cnt += week;

        // 更新剩餘數量
        for (int i = 0; i < N; i++)
            coins[i].number -= week * need[i];
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);

    cin >> N >> C;

    for (int i = 0; i < N; i++) {
        cin >> coins[i].value >> coins[i].number;
    }

    cout << solve() << endl;

    return 0;
}

amoshyc/poj3040.md

Poj 3040: Allowance

題目

分析

AC Code