UVa 10717 - Mint
传送门
题意
给出n种硬币的高度，给一个桌子垫脚，每个脚的硬币类型必须不同，最后要一样高。求不超过理想高度的最大值和大于等于理想高度的最小值。
思路
枚举所有四种硬币的LCM，一个一个比较。四层for，刚开始根本不敢写。还是看了一下别人的才敢。
求出LCM时，要求那两个值，KEDEBUG 的代码非常巧妙。
ans < tab[h].lev && tab[h].lev - tab[h].lev % ans
这个可以求出不超过lev的最大值
(ans - tab[h].lev % ans) % ans + tab[h].lev
这个求出超过lev的最小值。
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
const int INF = 0x3f3f3f3f;
#define LL long long
struct TABLE
{
LL low, high, lev;
TABLE(): low(0), high(INF) {}
};
LL coin[MAXN], n;
vector<TABLE> tab;
LL GCD(LL a, LL b)
{
return !b ? a : GCD(b, a % b);
}
LL Cal(LL a, LL b, LL c, LL d)
{
int i, j;
LL ans, temp;
ans = a / GCD(a, b) * b;
ans = ans / GCD(ans, c) * c;
ans = ans / GCD(ans, d) * d;
return ans;
}
void Solve()
{
int i, j;
for (i = 0; i < n; i++)
for (j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
for (int l = k + 1; l < n; l++)
{
LL ans = Cal(coin[i], coin[j], coin[k], coin[l]);
for (int h = 0; h < tab.size(); h++)
{
if (ans < tab[h].lev && tab[h].lev - tab[h].lev % ans > tab[h].low)
tab[h].low = tab[h].lev - tab[h].lev % ans;
if ((ans - tab[h].lev % ans) % ans + tab[h].lev < tab[h].high)
tab[h].high = (ans - tab[h].lev % ans) % ans + tab[h].lev;
}
}
for (i = 0; i < tab.size(); i++)
printf("%lld %lld\n", tab[i].low, tab[i].high);
}
int main()
{
//freopen("in.txt", "r", stdin);
int i, j, ntab;
TABLE temp;
while (scanf("%d%d", &n, &ntab), n + ntab)
{
tab.clear();
for (i = 0; i < n; i++)
scanf("%lld", &coin[i]);
for (i = 0; i < ntab; i++)
{
scanf("%lld", &temp.lev);
tab.push_back(temp);
}
Solve();
}
return 0;
}