题目传送门(BZOJ)

题解 :

暴力枚举分母, O(32767\times 2)来判定是否比当前答案更优即可
注意要求是不完全相同的分数

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define f2 doubleusing namespace std;const f2 eps = 1e-8;int ans1, ans2;int n, m;f2 now = 1e15, tar;inline f2 Abs(f2 x) {return x > 0 ? x : -x; }inline void calc(int i, int j) { if(i*m == j*n) return ; f2 fra = Abs((f2)i/j-tar); if(fra < now) { now = fra; ans1 = i, ans2 = j; }}int main() { scanf("%d%d", &n, &m); tar = (f2)n/m; for(int i = 1; i < 1<<15; i ++ ) { int j = i*n/m; calc(j, i), calc(j+1, i); } printf("%d %d\n", ans1, ans2);}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<