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

回答

相關問題