uva10717 - Mint(硬币做桌腿)

本文主要是介绍uva10717 - Mint(硬币做桌腿)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

就是求多个数的最小公倍数问题。。。。

思路不难，不过求最小公倍数的方法是刚学到的。。

（1）从n个硬币中，找四个类型的硬币组合，

（2）求每四个硬币厚度的最小公倍数

（3）在不同的选择下，记录最优答案。

代码如下：

#include <cstdio>
#define M 55
#define INF  0x7fffffff
int mint[M], select[4];
int n, t, h, L, R, ok;
int gcd(int a, int b)
{return b==0?a:gcd(b,a%b);
}
int lcm(int a, int b)
{if(a<b){int t = a; a = b; b = t;}return a/gcd(a,b)*b;
}
void solve()
{int Lcm = select[0];for(int i = 1; i < 4; i++) Lcm = lcm(Lcm,select[i]);int num, l, r;for(num = 1; Lcm*num <= h; num++); num-=1;if(Lcm*num==h) {L = R = h; ok = 1; return;}else {r = l = Lcm*num; r+=Lcm; }L = L < l ? l : L;R = R > r ? r : R;
}
void dfs(int p, int cur)
{if(ok) return;if(cur==4){solve();return ;}else for(int i = p; i <= n-4+cur; i++){select[cur] = mint[i]; dfs(i+1,cur+1);}
}
int main()
{while(scanf("%d%d",&n,&t),n+t){for(int i = 0; i < n; i++) scanf("%d",&mint[i]);for(int i = 0; i < t; i++){ok = 0;L = -INF;R = INF;scanf("%d",&h);for(int j = 0; ok==0&&j <= n-4; j++){select[0] = mint[j]; dfs(j+1,1);}printf("%d %d\n",L,R);}}return 0;
}

这篇关于uva10717 - Mint(硬币做桌腿)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---