round 931 div2 B题Yet Another Coin Problem补题

题意：给你1,3,6,10,15五种面值的硬币数量不限，给定一个数n，要求找出所需的最少数量的这些硬币，使它们的总价值相加正好是 n。

输入

第一行包含一个整数 t ( 1≤t≤1e4 ) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含一个整数 n ( 1≤n≤1e9) - 目标值。

输出

对于每个测试用例，输出一个数字，即所需硬币的最少数量。

思路：本来想用dp做，但是n的值太大了，用dp会mle，所以看了大佬的算法用暴力求解。因为这几个数字有一些倍数关系在，1面值最多取2个，如果有三个则会被一个3面值的代替，以此类推，那么面值3,6,10硬币的数量最多为1,4,3个，剩下的钱则全部用面值为15的填补，如果不能刚好填补，则说明当前方案行不通，继续枚举。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
void solve(int n)
{
	int ans=n;
	for(int i=0;i<3;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<5;k++)
				for(int q=0;q<3;q++)
				{
					int res=n-i-3*j-k*6-10*q;//前四种面值取完后剩下的钱
					if(res>=0&&res%15==0)//如果刚好等于n，则比较，取最小值
                        {ans=min(ans,res/15+i+j+k+q);}//否则该方案行不通，跳过
				}
	cout<<ans<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		solve(n);
	}
}