UVa11264 - Coin Collector(設計解題、貪心)

題目大意

有位愛好蒐集銅板的人想要透過銀行換錢的方式蒐集各式各樣的錢幣。但礙於銀行永遠都只會先給面額較大的錢幣，因此想請問你他最多可以蒐集多少錢幣。

假如有 1,5,10 這三種錢幣，如果我現在有 31 元，那我就會收到 2 個 10 元硬幣、1 個 1 元硬幣。

假如他身上有任意的錢，請告訴她，透過銀行匯款的方式他能夠收集到幾種貨幣。

題目連結

重點觀念

• 了解到能夠不斷給相同貨幣
• 了解絕對沒有辦法蒐集到全部的貨幣

分析

• 我們來觀察題目，以 1,3,6,8 為例
  • 我有 5 元時可以拿到 3,1,1 => 比 5 小的硬幣都有順利拿到
  • 我有 10 元時可以拿到 8,1,1 => 並沒有辦法順利地拿到 1,6,10
  • 我有 12 元時可以拿到 8,3,1 => 無法拿到 6 硬幣
• 觀察 A
  • 如果我想要拿到 6,8 這兩種硬幣，則 14 元可以做到
  • 如果我想拿到 1,6,7 這三種硬幣，則不可能做到。
    • \(1+6+7=14\)，\(14 = 7+7 \)
    • 如果 \(1+6 <= 7\)，那麼 1,6 硬幣沒有辦法同時出現，因為會被 7 取代
    • 如果 \(A+B <= C\)，那麼 A,B 硬幣沒有辦法同時出現，因為會被 C 取代
• 觀察 B，另一種可能性，以 1,3,6,8 為例
  • 我有 18 元時可以拿到 8,8,1,1 => 3,6 沒辦法拿到
  • 我有 10 元時可以拿到 8,1,1 => 3,6 沒辦法拿到
  • 這是因為 \(3+6 >= 8\)，因此沒有機會讓 3,6 同時被拿到。
  • 我們不可能讓 3,6 同時都存在，但我們可以讓 1,3 or 1,6 存在，這裡我們則是去除最大的硬幣。
• 結論
  • 小面額銅板的錢幣總和比當前硬幣小，則當前硬幣也可以變成一種組合(觀察A)
  • 小面額銅板的錢幣總和比當前硬幣大，換掉最大的小面額銅板，並加入現在的當前硬幣(觀察B)

參考連結

Uva11264 - Coin Collector by txya900619

心得

一個好題，複習我的英文能力，不然我的英文能力真的亂糟糟QQ。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 2000
using namespace std;
int t, n;
int num[MAXN];

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL

    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 0; i < n; i++) cin >> num[i];
        //sort(num, num+n); //題目本身就有排序

        int sum = 0, ans = 0;
        for(int i = 0; i < n; i++){ 
            if(num[i] > sum){ //觀察 A
                ans++;
                sum += num[i];
            }
            else sum = sum - num[i-1] + num[i]; //觀察 B
        }

        cout << ans << '\n';

    }
    return 0;
}