c - Code Jam 第 1A 轮 ProblemA 的 C++ 中的二分搜索

标签 c binary-search

我认为比赛分析中的代码片段不正确,while(right - left >= 1)可能会陷入无限循环。所以我使用 > 而不是 >=。但它没有给出正确的答案。

但是,代码通过了断言,这意味着左边是结果,右边是界限..我认为我的代码做了正确的事情,但是......

这是我的代码:

#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;
}

最佳答案

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

关于c - Code Jam 第 1A 轮 ProblemA 的 C++ 中的二分搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16351488/

相关文章:

c++ - 在 {8, 4, 6, 2} 中搜索 4 时,是否有任何 std::binary_search 的实现会返回 true?

c++ - Codechef 虫洞 : What's wrong with my logic?

java - java中的二分查找字符串

python - 在二分查找中,计算机如何选择中点以及何时只剩下两个元素

c - 16 位加法的 GCC -Wconversion 警告

c - 关于 vector 和函数的练习

c - C 中使用引用传递的矩阵加法

python - 在尝试计算每月最低还款额时,我的不断返回有点过高的值

c - 构建 C 应用程序?

c - 过于频繁地调用 Shell_NotifyIcon 后托盘图标停止出现