本文最后更新于 565 天前,其中的信息可能已经有所发展或是发生改变。
思想1:
- 暴力枚举。
- 枚举分子
i
和分母j
,利用eps
作为差值的最小值来判断更新条件。
代码:
#include <bits/stdc++.h>
using namespace std;
void solve(){
double a, b; int L;
cin >> a >> b >> L;
int aa, bb; double eps = 1e6;
for(int i = 1; i <= L; i ++){
for(int j = 1; j <= L; j ++){
double n = (double)i / j, m = a / b;
if(n >= m && n - m < eps) aa = i, bb = j, eps = n - m;
}
}
cout << aa << ' ' << bb << endl;
}
int main(){
solve();
return 0;
}
思想2:
- 二分。
- 枚举分子
i
,二分找到分母j
优化掉一层循环。
#include <bits/stdc++.h>
using namespace std;
void solve(){
double a, b; int L;
cin >> a >> b >> L;
int aa, bb; double eps = 1e6;
for(int i = 1; i <= L; i ++){
int l = 1, r = L;
double m = a / b;
while(l < r){
int mid = l + r + 1 >> 1;
double n = (double)i / mid;
if(n >= m) l = mid; //满足更新左边界
else r = mid - 1; //反之更新右边界
}
double n = (double)i / l;
if(n >= m && n - m < eps) aa = i, bb = l, eps = n - m;
}
cout << aa << ' ' << bb << endl;
}
int main(){
solve();
return 0;
}