题目解析

题意分析

这道题目要求我们计算如何用最少数量的硬币（$0.25$美元、$0.10$美元、$0.05$美元和$0.01$美元）来凑出给定的找零金额（以美分为单位）。具体规则如下：

1. 输入：

   • 第一行是测试数据集的数量 $N$（$1 \leq N \leq 100$）
   • 每个测试数据是一个整数 $C$（$1 \leq C \leq 500$），表示需要找零的金额（单位：美分）

2. 输出：

   • 对每个测试数据，输出数据集编号和最少硬币的组合，包括：
     • $Q$：$0.25$美元硬币的数量
     • $D$：$0.10$美元硬币的数量
     • $n$：$0.05$美元硬币的数量
     • $P$：$0.01$美元硬币的数量

3. 约束条件：

   • 必须使用最少数量的硬币
   • 找零金额不超过$5.00$美元（即$500$美分）

解题思路

1. 贪心算法：这是一个典型的贪心算法问题。为了用最少数量的硬币凑出给定的金额，我们应该优先使用面值较大的硬币。
2. 硬币面值：
   • $0.25$美元（$25$美分）
   • $0.10$美元（$10$美分）
   • $0.05$美元（$5$美分）
   • $0.01$美元（$1$美分）
3. 计算步骤：
   • 从最大的面值（$25$美分）开始，计算最多能用多少个该面值的硬币：$Q = C // 25$
   • 计算剩余金额：$C = C \% 25$
   • 对$10$美分硬币：$D = C // 10$
   • 剩余金额：$C = C \% 10$
   • 对$5$美分硬币：$n = C // 5$
   • 剩余金额即为$1$美分硬币数量：$P = C \% 5$

标程

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n;
    int i=1;
    while(n--)
    {
        cin>>m;
        int a=0,b=0,c=0,d=0;
        if(m>=25)
        {
            a+=m/25;
            m=m%25;
        }
        if(m>=10&&m<25)
        {
            b+=m/10;
            m=m%10;
        }
        if(m>=5&&m<10)
        {
            c+=m/5;
            m=m%5;
        }
        if(m>0&&m<5)
        {
            d+=m;
        }
        cout<<i++<<" "<<a<<" QUARTER(S), "<<b<<" DIME(S), "<<c<<" NICKEL(S), "<<d<<" PENNY(S)"<<endl;
    }
    return 0;
}