Codejam Round1A C++中的二进制搜索问题A

我认为比赛分析中的代码片段不正确，而（右 - 左> = 1）可能陷入无限循环。所以我使用>而不是> =。但它没有给出正确的答案。Codejam Round1A C++中的二进制搜索问题A

但是，代码经过断言，这意味着左边的是结果，右边是绑定的。我想我的代码做了正确的事情，但...

这里是我的代码：

#define _USE_MATH_DEFINES 

#include<cstdio> 
#include<cassert> 
#include<cmath> 

int main() 
{ 
    int cases; scanf("%d", &cases); 
    for(int c=1;c<=cases;c++) { 
    double r, t; 
    //long long t; 
    scanf("%lf %lf", &r, &t); 
    long long maxn = (long long)((sqrt((2*r-1)*(2*r-1)+8*t)-2*r+1)/4)+1; 
    long long left=0, right=1; 
    long long re= (long long)t; 
    while ((2*r-1)*right+right*right*2 <= t) { 
     left = right; right *= 2; 
    } 
    //printf("%lld\n",maxn); 
    while(left+1<right) { 
     long long m = left + (right - left)/2; 
     double tt = (2*r-1)*1.0*m+2*m*m; 
     if (tt<=t) 
     left=m; 
     else 
     right=m; 
    } 
    assert((2*r-1)*1.0*right+2*right*right>t); 
    assert((2*r-1)*1.0*left+2*left*left<=t); 
    printf("Case #%d: %lld\n", c, left); 
    } 
    return 0; 
}

来源

2013-05-03 Kan Liu

那么，你的问题是什么？我的帖子中没有看到任何内容。 – svick 2013-05-03 13:17:39

对不起..我无法找出为什么我的代码不适合大输入 – 2013-05-06 16:17:11

可能，double tt = (2*r-1)*1.0*m+2*m*m;正在失去精度。 double只有大约52位的整数精度。

来源

2013-05-10 01:20:16 xan

Codejam Round1A C++中的二进制搜索问题A

回答

相关问题