P1298 【最接近的分数】

· · 题解

题目大意

给出一个正小数，求值最接近这个小数且分子不超过 n ，分母不超过 m 的最简分数（若为整数 k 则输出 (k / 1) ）。如果分数不唯一，则输出 TOO MANY 。

思路

我真不知道搜索是怎么来的， 我第一想法是暴力枚举分子分母，但这样显然会 TLE (然而我玄学 MLE)。 那么需要思考别的算法。

后来想了想，发现可以直接从 1 到 m 枚举分母，然后用小数乘以分母再四舍五入即可得到分子。如果分子大于 n 则 break 。然后判断当前值是否比当前最优解优，若是则更新；若与最优解一致则判断这两个分数是否一样，若不一样则输出 TOO MANY。

另外要注意的是如果小数 ×1 都比 n 大，则输出 n / 1 。

代码

#include<bits/stdc++.h>
#define fr(i,a,b) for(register int i = a;i <= b;++i)
using namespace std;

double s;
int n,m,fz,fm;

inline int read(){
    int x = 0,f = 1;char c = getchar();
    while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}
    while(isdigit(c)){x = x * 10 + c - '0';c = getchar();}
    return f * x;
}

inline int gcd(int x,int y){return y ? gcd(y,x % y) : x;}

int main(){
    n = read(),m = read();scanf("%lf",&s);
    if(n == 0){printf("0/1\n");return 0;}
    fz = n;fm = 1;
    fr(i,1,m){
        int ans = (int)(1. * s * i + 0.5);
        if(ans > n)break;
        if(fabs(1. * ans / i - s) < fabs(1. * fz / fm - s)){
            fz = ans;fm = i;
            int g = gcd(fz,fm);
            fz /= g;fm /= g;
        }
        if(fabs(1. * ans / i - s) == fabs(1. * fz / fm - s)){
            int x = ans,y = i;
            int g = gcd(x,y);
            x /= g;y /= g;
            if(x != fz || y != fm){printf("TOO MANY\n");return 0;}
        }
    }
    printf("%d/%d\n",fz,fm);
    return 0;
}