ACM – Uva10717 – lcm+dfs

点击量:22

今天不适合刷题。。。

题意:一个桌子4条腿,每条腿由一种硬币构成,四条腿必须一样长,请问如何最接近给出的标准桌子高度,输出两个最接近的值。

更新两个值的时候错误的判断如果lcm大于h就不再更新了,却没有想到高于h的部分依然可以更新,只是不能更新小于h的部分了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int gcd(int a, int b)
{
    return b == 0? a: gcd(b, a % b);
}
const int maxn = 50 + 10;
int a[maxn];
int n, t;
int table[15];
int ans1[15];
int ans2[15];
void output()
{
    for(int i = 0; i < t; i++)
        printf("%d %d\n", ans1[i], ans2[i]);
}
// 寻找边界
bool findmax(int lcm, int num, int &mint, int &maxt)
{
    // if(lcm > num)
    // return false;
    int t = num / lcm * lcm;
    if(t == num)
    {
        mint = num;
        maxt = num;
    }
    else
    {
        mint = t;
        maxt = t + lcm;
    }
    // return 1;
}
// 检查
void check(int lcm)
{
    int mint, maxt;
    for(int i = 0; i < t; i++)
    {
        findmax(lcm, table[i], mint, maxt);
        if(ans1[i] == -1 || mint > ans1[i]) ans1[i] = mint;
        if(ans2[i] == -1 || maxt < ans2[i]) ans2[i] = maxt;
    }
}
// 枚举四个腿
void fs(int c, int num, int lcm)
{
    if(num == 4)
    {
        check(lcm);
        return;
    }
    for(int i = c; i < n; i++)
    {
        int temp = lcm;
        lcm = lcm / gcd(lcm, a[i]) * a[i]; // 可能溢出
        fs(i+1, num+1, lcm);
        lcm = temp;
    }
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    while(~scanf("%d%d", &n, &t) && n != 0)
    {
        for(int i = 0; i< n; i++) scanf("%d", &a[i]);
        for(int i = 0; i < t; i++)
        {
            scanf("%d", &table[i]);
            ans1[i] = -1;
            ans2[i] = -1;
        }
        fs(0, 0, 1);
        output();
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注