CF1934B题解

BinSky · 2024-03-02 18:26:45 · 题解

原题传送门

题目概述

你有 5 美元不同类型的硬币，每个硬币的价值等于前 5 美元三角形数字之一：1 美元、3 美元、6 美元、10 美元和 15 美元。这些硬币种类繁多。您的目标是找到所需的这些硬币的最小数量，使它们的总价值正好达到 n（保证答案存在）。

思路分析

这道题可以用暴力枚举+贪心的方式解决，但是直接枚举肯定超时，所以我们要减少枚举范围。例如为了让硬币数量最小，一元最多只能拿 2 个，因为拿 3 个可以用 1 个三元来代替；六元最多只能拿 4 个，因为拿 5 个可以用 2 个十五元来代替，以此类推。

代码

#include <bits/stdc++.h> 
using namespace std;
int main()
{
    int t,n;
    cin>>t;
    while(t--) 
    {
        int ans=0x3f3f3f3f;
        cin>>n;
     //枚举：
        for(int i1=0;i1<=2;i1++)
        {
            for(int i2=0;i2<=1;i2++)
            {
                for(int i3=0;i3<=4;i3++)
                {
                    for(int i4=0;i4<=2;i4++)
                    {
                        int s=n-i1-i2*3-i3*6-i4*10;
                        if(s>=0&&s%15==0)//满足条件剩下能用15元补充
                        {
                            ans = min(ans,i1+i2+i3+i4+(s/15));
                        }
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}