AOJ.849 分數 (暴力)

題意分析

每次枚舉分子，然後根據給出的分數值，推算出來分母，然後取分母上下幾個數進行進一步計算，看看哪個更接近。

一開始想着直接枚舉分子和分母，複雜度爆炸。。。

代碼總覽

#include <cstdio>
#include <algorithm>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
int gcd(int a,int b){while(b^=a^=b^=a%=b);return a;}
int main()
{
    int oup,odown;
    scanf("%d%d",&oup,&odown);
    double tar = 1.0*oup/odown;
    double bestnow = 0.0;
    double dis = INF;
    int up,down;
    for(int i =1 ;i<=32767;++i){
        double may = odown * i / oup;
        for(int k = 0; k<=1; ++k){
            int ret = (int)may + k;
            if(i == oup && ret == odown) continue;
            if((ret<=32767 && ret>=1))
                if(gcd(i,ret) ==1 ){
                    bestnow = i*1.0/ret;
                    if(fabs(bestnow - tar)<dis){
                        dis = fabs(bestnow - tar);up = i;down  = ret;
                    }
                }
        }
    }
    printf("%d %d",up,down);
    return 0;
}