UVa 11264 - Coin Collector

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

Solution

從最小的開始計算，每次加上當前幣值，確保可以換當前硬幣。
但如果加上去後會大於等於下一種錢幣，就會導致必須換幣值大的，這樣可能會減少原本可換的錢幣種數。
所以我們就捨去當前的，直接加上下一種，保證減去大的那個後，不會影響前面幣值較小能換的。

1 3 6 8 13 15

金額 => 可換的

1 => 1
1 + 3 => 3, 1
1 + 3 + 6 => 8, 1
1 + 3 + 8 => 8, 3, 1
1 + 3 + 8 + 13 => 15, 8, 1
1 + 3 + 8 + 15 => 15, 8, 3, 1

4 種

1 3 6 8 11 15 => 3 種

Code

UVa 11264

#include <cstdio>

int main()
{   
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, coin, last = 0, sum = 0, count = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &coin);
            if (sum >= coin)
                sum = sum - last + coin;
            else
            {
                sum += coin;
                ++count;
            }

            last = coin;
        }

        printf("%d\n", count);
    }

    return 0;
}