CF1934B Yet Another Coin Problem 题解

题意

目前有 \(5\) 种硬币，面值分别为 \(1,3,6,10,15\)。给你一个数字 \(n\)，求出可以凑出 \(n\) 的最少的硬币的数量。

思路

这道题，大多数的人大概会想到动态规划的方法。

但是，我们应该有敢于创新的精神。于是我就想到了一个简单的数学方法。

首先我们先不讨论面值等于 \(15\) 元的硬币。

考虑硬币的面值为 \(1\) 元、\(3\) 元、\(6\) 元、\(10\) 元、\(15\) 元的情况。

1：面值为 \(1\) 元的硬币的数量范围小于 \(3\)。

当使用大于等于 \(3\) 个 \(1\) 元硬币。

则可以用面值为 \(3\) 的硬币代替。

2：面值为 \(3\) 元的硬币的数量范围小于 \(2\)。

当使用大于等于 \(2\) 个 \(3\) 元硬币。

则可以用面值为 \(6\) 的硬币代替。

3：面值为 \(6\) 元的硬币的数量范围小于 \(4\)。

当使用大于等于 \(4\) 个 \(6\) 元硬币。

则可以用 \(2\) 个面值为 \(10\) 加 \(1\) 个面值为 \(3\) 加 \(1\) 个面值为 \(1\) 的硬币代替。

4：面值为 \(10\) 元的硬币的数量范围小于 \(3\)。

当使用大于等于 \(3\) 个 \(10\) 元硬币。

则可以用 \(2\) 个面值为 \(15\) 的硬币代替。

5：面值为 \(15\) 的硬币。

剩下的数目都有面值为 \(15\) 的硬币承担就好了。

时间复杂度

因为前面的数值都很少，所以时间复杂度也十分小。

代码

#include <bits/stdc++.h>
using namespace std;
int n,t,ans;
int main() {
	cin>>t;
	while(t--){
		cin>>n;
		ans=1000000000;
		for(int i=0;i<3;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<5;k++)
					for(int m=0;m<3;m++){
						int y=i*1+j*3+k*6+m*10;
						if(y>n)continue;
						if((n-y)%15==0){
							ans=min(ans,i+j+k+m+(n-y)/15);
						}
					}
		cout<<ans<<endl;
	}
}