有错误或不准确的二进制搜索

Question

首先，对不起我的英语。

我正在解决这个问题：

Tom wants to shoot from a cannon at the Jerry, but he would like to have as many pieces as possible, but they must be the same size and as big as possible too. He only have n cannonballs at his disposal, so he can cut them in smaller pieces. And he would like to have k + 1 pieces to shoot from cannon at the Jerry. He knows the radius of every cannonball. What is the biggest volume of one piece? Output is rounded printf("%.3f\n",answer). First number is n and the second k , next n numbers are radiuses of cannonballs. Possible input: 3 50 1 2 3 Output: 2.900*

这是我的解决方案：每一块的体积只能小于或等于最小炮弹的体积，因为你不能将炮弹的零件连接在一起。因此，我使用了从 0.0 到最小体积 的二进制搜索，并且作为谓词，我使用了函数 numberOfPieces，它计算每个炮弹的碎片数，具体 体积为 1 piece（这是二分查找的中位数）。如果我使用 median 作为一件的体积，这个函数 return 我可以获得的件数。然后我将它与 k + 1 进行比较，如果它更大或相等，我将中位数设为低值，否则我将其设为高值。 我的解决方案适用于此测试输入。

问题是我得到 WA（错误答案）并且我无法检查测试输入值。你能看看我的代码并检查我是否做错了什么吗？问题可能是数字不准确，但我的 EPS 很小，所以应该没问题。预先感谢您的每一个想法。

这是我的代码：

#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>

#define PI 3.14159265358979323846
#define VC ((4.0/3.0) * PI) // constant for volume calculation
#define EPS 1E-12

using namespace std;

// return the number of pieces depending on the volume
int numberOfPieces(int v[], int n, double volume)
{
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += (int)(v[i] * VC / volume);
    return ans;
}


double binarySearch(double a, double b, int k, int n, int v[])
{
   double low = a, high = b;
   while(abs(low-high) > EPS)
   {
      double mid = low + (high - low) / 2.0;
      if(numberOfPieces(v, n, mid) >= k)
          low = mid;
      else
          high = mid;
   }
   return (low + high)/2.0;
}

int main()
{
    int n, k, x; // n - number of cannonballs, k - number of wanted pieces, x - variable for input
    int v[10001]; // radiuses ^ 3 of the cannonballs
    scanf("%d%d", &n, &k);
    int minVolume = 9999999;
    for(int i = 0; i < n; i++) {
        scanf("%d",&x);
        minVolume = min(minVolume, x);
        v[i] = x * x * x;
    }
    printf("%.3f\n", binarySearch(0.0, minVolume * minVolume * minVolume * VC, k + 1, n, v));

    return 0;
}

Answer 1

问题是我在二进制搜索中将最小音量设置为高，但我应该使用最大音量。第二个问题是我没有将最大半径 ^ 3 传递给二进制搜索函数。感谢帮助

有错误或不准确的二进制搜索

Binary search with bug or inaccuracy

c++

algorithm

floating-accuracy

binary-search