BZOJ 1684: [Usaco2005 OCT]Close Encounter – [暴力]


题目传送门(BZOJ)

题解 :

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

代码 :

#include 
#include 
#include 
#include 
#define f2 double
using 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原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注