题解 P1298 【最接近的分数】

qwaszx · 2019-05-09 15:57:32 · 题解

暴力太不优雅了，来讲一种优雅的做法

有一种神奇的东西叫做Stern-Brocot树

先上图

(图片来自这里)

初始两个分数0/1和1/0，然后每次对于相邻的两个分数m/n和m'/n'，把(m+m')/(n+n')插入到它们中间.

可以证明它枚举了所有非负有理数.

对于任何阶段的相邻分数都有m'n-mn'=1，这可以通过归纳法证明.于是可以得到两个结论:

这两个性质可以保证构造出所有非负有理数，因为每往下走一层分子和分母中至少有一个会增加.

还有一点是这棵树是一个二叉搜索树

对于一个数x，寻找离他最近的分数只需要进行如下的操作:

int sgn(double x){return (x>eps)-(x<-eps);}
int lm=0,ln=1,rm=1,rn=0;
for(int mm=1,nn=1;mm<=m&&nn<=n;mm=lm+rm,nn=ln+rn)
{
    switch(sgn(x-1.*mm/nn))
    {
        case 0:{printf("%d/%d\n",mm,nn);return 0;}
        case 1:lm=mm,ln=nn;break;
        case -1:rm=mm,rn=nn;break;
    }
}

和二叉查找树操作差不多.

不过这样只是限定了x在[lm/ln,rm/rn]范围内，还需要判断一步才行.

实现上为了减小常数规避了除法.不过这题的数据看起来还是挺水的，优不优化一个样

复杂度O(n)，但实际上只有极大和极小的数会卡到这个级别，一般是O(\log n)左右的(斐波那契数列式增长?).

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const double eps=1e-15;
int n,m;double x;
int sgn(double x){return (x>eps)-(x<-eps);}
int main()
{
    scanf("%d%d",&m,&n);
    scanf("%lf",&x);
    int lm=0,ln=1,rm=1,rn=0;
    for(int mm=1,nn=1;mm<=m&&nn<=n;mm=lm+rm,nn=ln+rn)
    {
        switch(sgn(x*nn-mm))
        {
            case 0:{printf("%d/%d\n",mm,nn);return 0;}
            case 1:lm=mm,ln=nn;break;
            case -1:rm=mm,rn=nn;break;
        }
    }
    if(rn==0){printf("%d/%d\n",lm,ln);return 0;}
    switch(sgn((x-1.*lm/ln)-(1.*rm/rn-x)))
    {
        case 1:printf("%d/%d\n",rm,rn);break;
        case 0:puts("TOO MANY");break;
        case -1:printf("%d/%d\n",lm,ln);
    }
}

猜测rank1也是写的这个东西并且新评测姬跑得略慢(