c++ - 二进制搜索给出的结果略有不准确

Question

我要解决的问题如下:我得到了 N 个宽 1cm 长 C 的矩形纸条。我需要在切割 strip 的面积总和等于 A 的高度切割 strip 。您可以在下面看到一个示例，其中 N = 5， strip 的长度为 5、3、6、2 和 3 厘米，A = 3 厘米，其中切口是在 4cm 处制作。

请注意，我在这里寻找红色区域。

输入如下。每种情况的第一行都以两个整数 N (1 ≤ N ≤ 10^5) 和 A (1 ≤ A ≤ 10^9) 分别代表 strip 数和预期结果面积。下一行包含N个整数，代表每个 strip 的长度C_i(1 <= C_i <= 10^4)。 输入以 A = C = 0 结尾，不应处理。

对于每个测试用例，输出单行，必须进行切割的高度H，使得切割条的面积之和等于A平方厘米。打印小数点后 4 位的答案。如果不需要切割输出“:D”，如果不能切割则输出“-.-”。

这个问题可以查here

我解决这个问题的想法是使用二进制搜索，我在 strip 的中间选择一个高度，并根据我的切割是太高还是太低而使它变大或变小。我对问题的实现如下:

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

int main(){
    vector<int> v;  // Vector that holds paper heights
    int n;          // Number of papers
    double h,       // Height of the cut
           sum,     // Area sum
           min_n,   // Minimum height for cut to happen
           max_n,   // Maximum height for cut to happen
           a;       // Desired final area

    // Set desired output
    cout << fixed << setprecision(4);

    /* Get number of papers and desired area,
       terminates if N = A = 0
    */
    while(cin >> n >> a && (n||a)){
        v.resize(n); // Resize vector to fit all papers
        // Get all paper sizes
        for(int i=0;i<n;i++){
            cin >> v[i];
        }
        /* Sort the vector in decreasing order to
           simplify the search
        */
        sort(v.begin(),v.end(),greater<int>());
        max_n = v[0]; // Largest possible cut is at the height of the largest paper
        min_n = 0; // Smallest possible cut is at the base with height 0

        // Iterate until answer is found
        while(true){
            // Initialize cut height as the average of smallest and largest cut sizes
            h = (min_n + max_n)/2;

            /* The area sum is equal to the sum of the areas of each cut, which is
               given by the height of the paper minus the cut height. If the cut is
               higher than the paper, the cut has area 0.
            */
            sum = 0;
            // Using mascoj sugenstion, a few changes were added
            int s; // Temporary variable to hold number of time h is subtracted
            for(int i=0; i<n;i++){
                if(v[i] <= h) break; // From here onward cut area is 0 and there is no point adding
                sum += v[i]; // Removed the subtraction inside of the for loop
                s++; // Count how many paper strips were used
            }
            sum -= h*s // Subtracts the area cut from the s paper strips

            // If the error is smaller than the significant value, cut height is printed
            if(std::abs(sum-a) < 1e-5){
                // If no cut is needed print :D else print cut height
                (h < 1e-4 ? cout << ":D" << endl : cout << h << endl);
                break;
            }
            // If max_n is "equal" to min_n and no answer was found, there is no answer
            else if(max_n - min_n < 1e-7){
                cout << "-.-" << endl;
                break;
            }
            // Reduces search interval
            sum < a ? max_n = h : min_n = h;
        }
    }
    return 0;
}

问题是，在提交答案后，我一直收到 10% 的错误。该网站有一个工具可以将您的程序输出与预期输出进行比较，因此我运行了一个包含 1000 多个随机生成的测试用例的测试文件，当我比较两者时，我在小数点后 4 位出现舍入错误，不幸的是，我没有没有文件或脚本可以为我生成测试用例了。我尝试将可接受的错误更改为更小的错误，但这没有用。我似乎找不到错误，你们中有人知道发生了什么吗？

ps:虽然问题描述上没有说，但是可以得到以分数为高度的cut

Answer 1

可能是您的问题，也可能不是:这一行加剧了浮点错误:sum += v[i]-h;

float 非常准确，并且在更大的总和上增加这个错误。我会尝试在 h 上使用乘法，然后从适用长度的总和中减去它。应该在 double 格式的范围内，所以我不会担心超出格式。