[19]硬币兑换-美团点评2018秋

1.题目描述

A国一共发行了几种不同面值的硬币，分别是面值1元，2元，5元，10元，20元，50元，100元。假设每种面值的硬币数量是无限，现在你想用这些硬币凑出总面值为n的硬币，同时你想让选出的硬币中，不同的面值种类尽可能多；在面值种类尽可能多的情况下，你想让选择的硬币总数目尽可能多，请问应该怎么选择硬币？

• 输入描述：
  第一行包含一个数字𝑛，表示要凑出的面值。1≤𝑛≤109
• 输出描述：
  输出两个整数，分别表示最多能有多少种类型的硬币以及在类型最多的情况下最多能用上多少枚硬币。
• 输入样例 1：

  3
  

• 输出样例 1：

  2 2
  

• 输入样例 2：

  10
  

• 输出样例 2：

  3 5
  

样例解释：在样例2中，最优的选择方法是3枚面值为1的，1枚面值为2的，1枚面值为5 的。

2.题目解析

首先，确定面值𝑛最多能有多少种面值。然后从大到小，每种面值的硬币用一个，剩下的全部用面值为1的硬币填充。

硬币个数	0	1	2	3	4	5	6	7
最少金额	0	1	3	7	17	27	77	177

3.参考答案

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n = 0;
  scanf("%d",&n);
  
  const int coins[] = {0, 1, 2, 5, 10, 20, 50, 100}; // 硬币种类
  int sum[8];// 下标代表币种数
  sum[0] = 0;
  // 统计每种不同种类组合最小总和
  for(int i=1;i<8;++i){
      sum[i] = coins[i]+sum[i-1];
  }
  
  for(int i=7;i>0;--i){
      if(sum[i] <= n){
          // i表示使用币种数
          // n - sum[i]表示剩余使用1元的数目
          printf("%d %d\n",i,n-sum[i]+i);
          break;
      }
  }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 0;
    scanf("%d",&n);

    int sum[8] = {0,1,3,8,18,38,88,188};// 下标表示硬币数量，值表示在i个硬币下组成的最小数额
    for(int i=7;i>=0;--i){
        if(sum[i] <= n){
            printf("%d %d\n",i, n-sum[i]+i);
            return 0;
        }
    }
}

牛客题目