题解 | 日本旅行

解题思路

基本思路：
- 使用贪心算法从大到小的面值尝试使用硬币。
- 尽量使用面值大的硬币，以减少硬币的数量。
- 在每种面值的硬币中，使用尽可能多的硬币，但不能超过可用的数量。
实现方法：
- 从500元硬币开始，依次尝试100元、50元、10元、5元和1元硬币。
- 计算所需的硬币数量，并更新剩余金额。
- 如果在所有硬币使用后仍有剩余金额，则返回"NOWAY"。

代码

cpp
java
python

#include <iostream>
using namespace std;

int main() {
    long long C1, C5, C10, C50, C100, C500, A;
    cin >> C1 >> C5 >> C10 >> C50 >> C100 >> C500 >> A;

    long long coins[] = {500, 100, 50, 10, 5, 1};
    long long counts[] = {C500, C100, C50, C10, C5, C1};
    long long totalCoins = 0;

    for (int i = 0; i < 6; i++) {
        long long coinValue = coins[i];
        long long coinCount = counts[i];

        if (A >= coinValue) {
            long long needed = A / coinValue; // 需要的硬币数量
            long long used = min(needed, coinCount); // 实际使用的硬币数量
            totalCoins += used; // 更新总硬币数量
            A -= used * coinValue; // 更新剩余金额
        }
    }

    if (A == 0) {
        cout << totalCoins << endl; // 输出所需的最少硬币数量
    } else {
        cout << "NOWAY" << endl; // 如果无法凑出金额
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long C1 = sc.nextLong();
        long C5 = sc.nextLong();
        long C10 = sc.nextLong();
        long C50 = sc.nextLong();
        long C100 = sc.nextLong();
        long C500 = sc.nextLong();
        long A = sc.nextLong();

        long[] coins = {500, 100, 50, 10, 5, 1};
        long[] counts = {C500, C100, C50, C10, C5, C1};
        long totalCoins = 0;

        for (int i = 0; i < 6; i++) {
            long coinValue = coins[i];
            long coinCount = counts[i];

            if (A >= coinValue) {
                long needed = A / coinValue; // 需要的硬币数量
                long used = Math.min(needed, coinCount); // 实际使用的硬币数量
                totalCoins += used; // 更新总硬币数量
                A -= used * coinValue; // 更新剩余金额
            }
        }

        if (A == 0) {
            System.out.println(totalCoins); // 输出所需的最少硬币数量
        } else {
            System.out.println("NOWAY"); // 如果无法凑出金额
        }
    }
}

def min_coins(C1, C5, C10, C50, C100, C500, A):
    coins = [500, 100, 50, 10, 5, 1]
    counts = [C500, C100, C50, C10, C5, C1]
    total_coins = 0

    for coin_value, coin_count in zip(coins, counts):
        if A >= coin_value:
            needed = A // coin_value  # 需要的硬币数量
            used = min(needed, coin_count)  # 实际使用的硬币数量
            total_coins += used  # 更新总硬币数量
            A -= used * coin_value  # 更新剩余金额

    if A == 0:
        return total_coins  # 返回所需的最少硬币数量
    else:
        return "NOWAY"  # 如果无法凑出金额

if __name__ == "__main__":
    C1, C5, C10, C50, C100, C500, A = map(int, input().split())
    result = min_coins(C1, C5, C10, C50, C100, C500, A)
    print(result)

算法及复杂度

算法：贪心算法
时间复杂度： $\mathcal{O}(1)$ ，因为硬币种类固定
空间复杂度： $\mathcal{O}(1)$ ，只使用常数额外空间