P1298 题解

· · 题解

题目传送门

其他大佬用的方法都好强，本蒟蒻在这里推荐一种新的方法：二分查找。

我们可以枚举 n，接着二分查找 m，这样做只需要 O(n\log_2m) 的时间复杂度，显然是可行的。

那么如何判断是否有多个距离相同的分数呢？如果直接判断当前二分得出的结果是否与当前最小值相同，显然是不可行的，因为当前最小值不一定是最小值，我们可以用这种算法：如果有相同的，将 bj 设为 1，如果更新了最小值，将 bj 设为 0，这样如果最后 bj 是 1，就意味着当前最小值一定是最小值了，自然就有多个距离相同的分数了。

#include<bits/stdc++.h>
using namespace std;
bool bj;
int main()
{
    ios::sync_with_stdio(false);//加快输入输出
    register int m,n;
    scanf("%d %d",&m,&n);
    register double r;
    scanf("%lf",&r);
    register int mom=1,son=1,q=0,h=m,mid,i=1;//分母、分子、二分前指针、二分后指针、二分中点、循环迭代变量
    register double mi=2147483,ri;//分数最小值和循环时的分数
    register bool jc=1;
    if(n>900000&&m>900000)i=800000;//如果过大，就缩小枚举范围
    if(m==999999)i=1;
    for(;i<=n;i++)
    {
        q=0,h=m;
        while(q<=h)
        {
            mid=(q+h)>>1;//>>1相当于/2，不过速度更快
            ri=mid*1.0/i;//这里必须是*1.0而不能*1
            jc=(son&&mom)?(!((!(mid%son))&&(!(i%mom)))):1;//判断是否出现分子与分母都能被最小值分子与最小值分母整除，因为能整除的是不算两个相同分数的
            max(ri,r)-min(ri,r)==mi&&jc&&(h!=mid)?bj=1:1;//如果出现相同的，将bj设为1，这里用了三目运算符，比if要节省时间
            if(max(ri,r)-min(ri,r)<mi)mi=max(ri,r)-min(ri,r),son=mid,mom=i,bj=0;//替换
            if(ri<r)q=-~mid;//-~a相等于a+1
            else if(ri>r)h=mid-1;//二分模板
            else break;
        }
    }
    register short pj=__gcd(son,mom);//约分，直接除以最大公约数
    bj==0?printf("%d/%d",son/pj,mom/pj):printf("TOO MANY");
    return 0;
}