Двоичный поиск дал несколько неточные результаты

Question

Проблема, которую я пытаюсь решить, следующая: я получаю N прямоугольные бумажные полоски шириной и длиной 1 см C. Мне нужно разрезать полоски на высоте, где сумма площадей разрезаемой полосы равна A. Вы можете увидеть пример нижнего ребра, для которого N = 5, полоски имеют длину, 5,3,6,2 и 3 см и A = 3 см, где разрез сделан на 4 см.

Обратите внимание, что я ищу здесь для красной области.

Вход задается следующим образом. Первая строка в каждом случае начинается с двух целых чисел N (1 ≤ N ≤ 10^5) и (1 ≤ ≤ 10^9), представляющих соответственно количество полос и ожидаемый в результате площадь , Следующая строка содержит N целых чисел, представляющих длину C_i (1 < = C_i < = 10^4) каждой полосы. Вход заканчивается A = C = 0, который не должен обрабатываться.

Для каждого теста вывести в одной строке, высота Н разреза, что должно быть сделано так, чтобы сумма площади отрезанных полос равна cm². Распечатайте ответ с 4 знаками после запятой. Выход «: D», если резка не требуется, или «-.-», если это невозможно.

Эта проблема может быть найдена here

Моя идея для решения этой проблемы в том, чтобы использовать бинарный поиск, где я поднимаю высоту в середине полосы и сделать его больше или меньше в зависимости от того, был ли мой разрез слишком высокий или слишком низкий. Моя реализация задачи дается ниже:

#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-м десятичном разряде, к сожалению, У меня есть файл или сценарий для создания тестовых примеров для меня. Я попытался изменить приемлемую ошибку на меньшую, но это не сработало. Кажется, я не могу найти ошибку, у любого из вас есть представление о том, что происходит?

пс: Несмотря на то, что проблема не говорит по описанию, вы можете получить порезы фракциях как высоты

Answer 1

может быть ваша проблема, возможно, не так: ошибка Эта линия усугубляя с плавающей точкой: sum += v[i]-h;

Плавающие точки являются настолько точными и усугубляют эту ошибку при увеличении суммарного суммирования. Я попытался бы использовать умножение на h и вычитал бы это из общей суммы применимых длин. Должно быть в пределах диапазона формата двойной точности, поэтому я не стал бы беспокоиться о превышении формата.

Answer 2

Не уверен, что понял ваш алгоритм, но я думаю, что это можно сделать намного проще, используя карту вместо вектора.

В следующем примере карта mp запоминает, сколько (значений) полосок имеет заданную длину (ключ).

Приобретено преимущество карты.

Далее вы можете увидеть, сколько вам нужно сэкономить (не для кошки), и рассчитать уровень разреза, начинающийся с нуля, добавив 1, когда это необходимо, и при необходимости добавьте дробь.

Надежда следующий пример может помочь

#include <map> 
#include <iomanip> 
#include <iostream> 

int main() 
{ 
    int       n; 
    int       n2; 
    int       v; 
    int       cut; 
    int       a; 
    std::map<int, std::size_t> mp; 
    long long int    sum; 
    long long int    ts; 


    std::cout << std::fixed << std::setprecision(4); 

    while((std::cin >> n >> a) && (n || a)) 
    { 
     mp.clear(); 

     n2 = 0; 
     sum = 0LL; 

     for (auto i = 0 ; i < n ; ++i) 
     { 
     std::cin >> v; 

     if (v > 0) 
      { 
      sum += v; 

      ++mp[v]; 
      ++n2; 
      } 
     } 

     // mp is a map, so the values are ordered 

     // ts is "to save"; sum of lenghts minus a 
     ts = sum - a; 

     // cut level 
     cut = 0; 

     // while we can add a full cm to the cut level 
     while ((ts > 0LL) && (n2 > 0) && (ts >= n2)) 
     { 
     ++cut; 

     ts -= n2; 

     if (cut >= mp.cbegin()->first) 
      { 
      n2 -= mp.cbegin()->second; 

      mp.erase(mp.cbegin()); 
      } 
     } 

     if ((ts == 0LL) && (cut == 0)) 
     std::cout << ":D" << std::endl; // no cut required (?) 
     else if (n2 == 0) 
     std::cout << "-.-" << std::endl; // impossible (?) 
     else 
     std::cout << (cut + double(ts)/n2) << std::endl; 
    } 
} 

p.s .: Заметим, что a определяется как целое число на странице, что Вы связываетесь.