Exact Change （贪心枚举）

D. Exact Change

[link](Problem - D - Codeforces)

题意

给你一些数，你有 1 元、 2 元、三元 1元、2元、三元 1元、2元、三元三种硬币，问你最少带多少个硬币可以将这些数都可以分别凑出来。

思路

贪心的来看我们能多用 3 3 3就多用 3 3 3， 3 的余数最多有 0 , 1 , 2 3的余数最多有0,1,2 3的余数最多有0,1,2，也就是我们最多带再带一个 1 ，一个 2 一个1，一个2 一个1，一个2就能把所有的都拼出来，所以上界为 m a x n u m / 3 + 2 maxnum / 3 + 2 maxnum/3+2。但有的时候并不需要 1 或 2 1或2 1或2，还有的时候可以少带一个 3 3 3将一个余数为 1 1 1的转化为用两个 2 2 2拼出，例如 10 , 8 10,8 10,8最优解因该是 3 , 3 , 2 , 2 3,3,2,2 3,3,2,2四个硬币即可。

发现贪心下界分类讨论不是很方便，但是经过刚才分析，我们发现，最多用一个 1 1 1，最多用两个 2 2 2，因此我们暴力的枚举用多少个 1 和 2 1和2 1和2，然后枚举每一个数判断一下当前用了这些 1 , 2 1,2 1,2后还需要多少个 3 3 3即可，注意一定是可以凑出的情况我们才比较，如果凑不出即当前选法无解置成正无穷即可。

Code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
#include 
#include 
#include  
#include 
#define x first
#define y second
#define debug(x) cout<<#x<<":"< PII;
typedef pair PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T -- ) {
		cin >> n;
		for (int i = 0; i < n; i ++) cin >> a[i];
        
		int res = INF;
		for (int x1 = 0; x1 <= 1; x1 ++)	
			for (int x2 = 0; x2 <= 2; x2 ++) {
				int ans = 0;
				for (int i = 0; i < n; i ++) {
					int cnt = INF;
					for (int sx1 = 0; sx1 <= x1; sx1 ++)
						for (int sx2 = 0; sx2 <= x2; sx2 ++) {
							int v = a[i] - sx1 - sx2 * 2;
							if (v >= 0 && v % 3 == 0) {
								cnt = min(cnt, v / 3);
							}
						}
				ans = max(ans, cnt);
			}
			res = min(res, ans + x1 + x2);
	}
        
		cout << res << endl;
	}
	return 0;
}

Exact Change （贪心枚举）

C/C++/C#相关栏目本月热门文章