Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一感觉:枚举分母的二分解法 32ms

Posted by 947186602 at 2020-08-31 21:13:06 on Problem 1650
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator