2015湘潭邀请赛 D.Fraction

刻骨铭心的一道题
http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1236

当时比赛的时候就是卡在了这道题目上，大sb题，其实当时就是把题目的条件理解多了一层意思
If several fractions satifies the restriction, he chooses the smallest one with simplest formation.
就是这句话，当时理解的是取的是值最小且误差最小，但实际这种语法指的就是误差最小！！！坑爹啊，现场赛时候最后都没意识到这点，还浪费了那么多的时间！

#include<bits/stdc++.h>
using namespace std;
double x;
int main(){
    int t;cin>>t;int a,b;
    while(t--){
        scanf("%lf",&x);double minn=100000000.0;
        for(int i=1;i<=1000;i++){
            double ans=i*x;
            int d=(int)ans;
            if(fabs((double)d/(double)i-x)<minn){
                minn=fabs((double)d/(double)i-x);
                a=d;b=i;
            }
            if(fabs((double)(d+1)/(double)i-x)<minn){
                minn=fabs((double)(d+1)/(double)i-x);
                a=d+1;b=i;
            }
        }
        printf("%d/%d\n",a,b);
    }
}

也可以这么做：
思路：分母不大于1000，直接预处理出所有的a/b，gcd(a,b) = 1，排序。对于输入的每个分数，直接二分查找，最接近的肯定是不小于它的最小的那个分数或者不大于它的最大的那个分数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;

const int N = 1010;
struct point
{
    int x,y;
    double z;
    friend bool operator < (const point &p,const point &q) {
        return p.z < q.z;
    }
}a[N * N];

int main()
{
    int cnt = 0;
    for(int i = 1; i <= 1000; i ++) {
        for(int j = 0; j <= i; j ++) {
            if(__gcd(i,j) != 1) continue;
            a[cnt].x = j,a[cnt].y = i,a[cnt].z = 1.0 * j / i;
            cnt ++;
        }
    }
    sort(a,a + cnt);
    int t;
    scanf("%d",&t);
    while(t --) {
        double x;
        scanf("%lf",&x);
        int idx = cnt - 1,lt = 0,rt = cnt - 1,mid;
        while(lt <= rt) {
            mid = lt + rt >> 1;
            if(a[mid].z >= x) {
                idx = mid;
                rt = mid - 1;
            }
            else lt = mid + 1;
        }
        if(fabs(a[idx - 1].z - x) < fabs(a[idx].z - x)) {
            printf("%d/%d\n",a[idx - 1].x,a[idx - 1].y);
        }
        else printf("%d/%d\n",a[idx].x,a[idx].y);
    }
    return 0;
}