最接近的分数-题解

emmmmm…… 感觉这道题就是一个暴力……

首先，由于n和m的范围都很大，所以直接枚举n和m会超时，所以我们需要换一种思路，那就是之枚举一个。 因为我们要使x/y的值与a的值最接近，所以当x/y = a时，x = a * y，所以我们只需要枚举y的值即可。由于实数转整数的时候比较迷，所以我们要分别向上和向下取整 ps：别忘了TOO MANY的特判附一下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define INF 0x7fffffff
#define ll long long

using namespace std;
int read()
{
    int x = 0,f = 1; char ch;
    ch = getchar();
    while(ch >’9’ || ch < ‘0’){if(ch == ‘-‘) f = -f; ch = getchar();}
    while(ch >= ‘0’ && ch <= ‘9’){x = x * 10 + ch - ‘0’; ch = getchar();}
    return x * f;
}
int gcd(int a, int b){return a == 0 ? b : gcd(b % a, a);}
int n,m,x,u,pd,g,oo;
double a,k,Min = INF,j,te;
int work1(int i)
{
    k = a * i;
    u = k;
    k = u + 1;
    te = k / i;
    j = fabs((k / i) - a);
}
int work2(int i)
{
    k = a * i;
    u = k;
    k = u;
    te = k / i;
    j = fabs((k / i) - a);
}
int main()
{
    m = read();
    n = read();
    cin >> a;
    for(re int i  = 1; i <= n; i++)
    {
        work1(i);
    if(j &lt; Min &amp;&amp; u &lt;= m)
    {
        Min = j;
        x = i;
        pd = 0;
        oo = te * x; 
    }
    work2(i);
    if(j == Min &amp;&amp; u &lt;= m) pd = 1;
    if(j &lt; Min &amp;&amp; u &lt;= m)
    {
        Min = j;
        x = i;
        pd = 0;
        oo = te * x; 
    }
}
if(a &lt; 0.5&amp;&amp; (m &lt; 2 || n &lt; 2))
{
    printf("TOO MANY\n");
    return 0;
}
double ans1 = a * x,ans2 = a * x + 1;
int ans = ans1;
ans2 = ans;
if(fabs(ans2/x - a) &gt; fabs((ans2 + 1)/x - a)) ans ++;
g = gcd(x,ans);
if(g ==0) g = 1;
if(x == 0)
{
    cout &lt;&lt;"1/1"&lt;&lt; endl;
    return 0;
}
printf("%d/%d\n",ans / g, x / g);
return 0;
}