c317: 硬幣問題！前傳

2019-08-23

內容

小明買了 X 元的商品，要付錢發現他只有兩種硬幣，幣值分別為 a 元和 b 元。

他希望用最少的硬幣湊到「剛好」X 元，請告訴小明最少需要用多少硬幣。

輸入

第一行有一個整數 N (N <= 1,000)，表示接下來會有 N 筆輸入

接下來 N 行，每一行有三個整數 X, a, b 表示小明要用 a, b 兩種幣值的硬幣湊出 X 元

(1000>= X >= a >= b >= 1)

3
258 24 20
144 11 3
309 24 9

輸出

如果可以剛好湊到 X 元，請輸出最少需要的硬幣數量。

如果沒辦法剛好湊到，請輸出 -1。

-1
16
16

解題思路

由於硬幣只有兩種，故若能形成目標值，額度較大的硬幣數越多，則需要用到的硬幣就越少。

因題目規定 a >= b，所以先找到 a 硬幣最多需要幾個才會超過目標值(x)，之後迴圈用 a 去遞 x 並將其用 b 試除，若餘 0 代表可用這兩種硬幣達成目標值，再加上上面的規則，因此該組合即為答案，輸出該組合的硬幣數即可。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>

int main()
{
    int n, target, coin1, coin2, i, sum, count;
    while (scanf(" %d", &n) == 1)
    {
        while (n--)
        {
            scanf(" %d %d %d", &target, &coin1, &coin2);
            i = target / coin1, count = -1;
            sum = coin1 * (i + 1);
            for (; i >= 0; i--)
            {
                sum -= coin1;
                if ((target - sum) % coin2 == 0)
                {
                    count = i + (target - sum) / coin2;
                    break;
                }
            }
            printf("%d\n", count);
        }
    }
    return 0;
}