题解 | #硬币兑换#
硬币兑换
https://www.nowcoder.com/practice/4f900b1c941c45288dba06baa006907f
解题思路
- 题目要求用
面值的硬币凑出目标金额
- 需要同时满足两个优化目标：
- 使用的不同面值种类尽可能多
- 在种类最多的情况下，使用的硬币总数尽可能多
- 解题策略：
- 从小到大遍历每种面值（除1元外）
- 如果剩余金额大于等于当前面值，则使用该面值
- 使用1元硬币补齐剩余金额
代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int coins[] = {2, 5, 10, 20, 50, 100};
int typeCount = 1; // 已经包含1元硬币
int remaining = n - 1; // 减去一个1元硬币
int totalCoins = n; // 初始假设全用1元
// 尝试使用每种面值的硬币
for(int i = 0; i < 6; i++) {
if(remaining < coins[i]) {
break;
}
typeCount++;
remaining -= coins[i];
totalCoins = totalCoins - coins[i] + 1;
}
cout << typeCount << " " << totalCoins << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] coins = {2, 5, 10, 20, 50, 100};
int typeCount = 1; // 已经包含1元硬币
int remaining = n - 1; // 减去一个1元硬币
int totalCoins = n; // 初始假设全用1元
// 尝试使用每种面值的硬币
for(int i = 0; i < 6; i++) {
if(remaining < coins[i]) {
break;
}
typeCount++;
remaining -= coins[i];
totalCoins = totalCoins - coins[i] + 1;
}
System.out.println(typeCount + " " + totalCoins);
}
}
n = int(input())
coins = [2, 5, 10, 20, 50, 100]
type_count = 1 # 已经包含1元硬币
remaining = n - 1 # 减去一个1元硬币
total_coins = n # 初始假设全用1元
# 尝试使用每种面值的硬币
for coin in coins:
if remaining < coin:
break
type_count += 1
remaining -= coin
total_coins = total_coins - coin + 1
print(f"{type_count} {total_coins}")
算法及复杂度
- 算法：贪心算法
- 时间复杂度：
- 硬币面值种类是固定的，只需遍历一次
- 空间复杂度：
Momenta公司福利 615人发布