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