NEFU-1643 比例简化

NEFU-1643 比例简化

/ 0评 / 1266次 / 0

Description

在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某观点表示支持的有 1498 人,反对的有 902 人,那么其比例可以简单地记为1498∶902。 因该比例的数值太大,难以一眼看出它们的关系。若把比例记为 5∶3,虽然与真实结果有一定的误差,但依然能够较为准确地反映调查结果,同时也显得比较直观。 现给出支持人数 A 和反对人数 B,以及一个上限 L,请将 A 比 B 化简为 A′ 比 B′,要求在 A′和 B′ 均不大于 L,且 A′ 和 B′ 互质(两个整数的最大公约数为 1)的前提下,A′/B′≥ A/B 且 A′/B′-A/B 的值尽可能小。

Input

一行三个整数 A,B,L,每两个整数之间用一个空格隔开,分别表示支持人数、反对人数以及上限。

Output

一行两个整数 A′ 和 B′,中间用一个空格隔开,表示化简后的比例。

Accepted Code

#include <bits/stdc++.h>
using namespace std;
int gcd(int x, int y)   //欧几里得算法求最大公因数
{
    int rem = 0;
    while (y > 0)
    {
        rem = x % y;
        x = y;
        y = rem;
    }
    return x;
}
int main()
{
    double a, b, l;
    cin >> a >> b >> l;
    double h = a / b;
    double minm = 1000;
    int ans1 = 1, ans2 = 1;
    for (int a1 = 1; a1 <= l; a1++)  //双循环暴力枚举获取两数的所有可能
    {
        for (int b1 = 1; b1 <= l; b1++)
        {
            if (((double)a1 / (double)b1 >= h) && (minm - h > ((double)a1 / (double)b1) - h))
            {
                minm = (double)a1 / (double)b1;
                ans1 = a1;
                ans2 = b1;
            }
        }
    }
    int y = gcd(ans1, ans2);
    cout << ans1 / y << " " << ans2 / y << endl;
    return 0;
}

解后反思

本题略为有趣,本蒟蒻WA了足足五次,后来一顿乱改就过了,评测姬玄学错误。

再说这一题,暴力复杂度大约是1e4,完全可以接受,那就暴力遍历枚举,记录下差值,获取最小的一组最后gcd化简即可

发表回复

您的电子邮箱地址不会被公开。

你好 No.63965