| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
第一感觉:枚举分母的二分解法 32ms#include<cstdio>
#include<math.h>
#define EPS 1e-14
using namespace std;
double A;
int N,D,L;
int min(int x,int y){
return x < y ? x : y;
}
int main()
{
while(~scanf("%lf%d",&A,&L))
{
double res = 0x3f3f3f3f;
int min_n = 1,min_d = 1;
for(int i = 1; i <= L; ++i)
{
D = i; //分母
int lb = min((int)A * D - 1,L-1),ub = min((int)(A+1) * D + 1,L+1); //尝试扩大分子,减少计算量,注意不要超过L
if(lb < 0) lb = 0;
while(ub - lb > 1)//双开写法
{
int mid = lb + (ub - lb) / 2;
double y = (mid * 1.0) / (D * 1.0);
double now = fabs(A - y);
if(res > now + EPS)
{
res = now;
min_n = mid;
min_d = D;
}
if(A + EPS < y)
{
ub = mid;
}
else lb = mid;
}
}
printf("%d %d\n",min_n,min_d);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator