看不懂二分查找功能

Question

帮我理解二分查找在这道题中的用法： Problem

Write a class FairWorkload with a method getMostWork which takes a int[] folders (the number of folders for each filing cabinet) and an int workers (the number of workers). The method should return an int which is the maximum amount of folders that a worker would have to look through in an optimal partitioning of the filing cabinets.

密码是

int getMostWork( vector  folders, int workers ) {
    int n = folders.size();
    int lo = *max_element( folders.begin(), folders.end() );
    int hi = accumulate( folders.begin(), folders.end(), 0 );

    while ( lo < hi ) {
      int x = lo + (hi-lo)/2;

      int required = 1, current_load = 0;
      for ( int i=0; i<n; ++i ) {
         if ( current_load + folders[i] <= x ) {
            // the current worker can handle it
            current_load += folders[i];
         }
         else {
            // assign next worker
            ++required;
            current_load = folders[i];               
         }
      }

      if ( required <= workers )
         hi = x;
      else
         lo = x+1;
    }

    return lo;
}

我没听懂：

 if ( required <= workers )
    hi = x;
 else
    lo = x+1;

有人可以向我解释这段代码和这一部分吗？

Answer 1

这里使用二分搜索来找到最优的 solution.For 二分搜索你需要一个由 high 和 low 表示的范围。你知道最优答案就在这个 range.In 这个特殊问题 low 由工作人员必须查找的最小文件夹数表示，这将是文件柜中的最大文件夹数

int lo = *max_element( folders.begin(), folders.end() );

high 如果只有一名工作人员被分配了所有文件夹，这些文件夹将是 folders

中所有值的总和

int hi = accumulate( folders.begin(), folders.end(), 0 );

现在你遍历这个范围并尝试找到最佳答案。

 while ( lo < hi ) {
      int x = lo + (hi-lo)/2;

在循环的每次迭代中，如果为每个工作人员提供最多 x 个文件夹，您将检查所需的工作人员数量。然后，您通过检查是否能够满足约束 x 作为解决方案来决定下一个范围，并尝试获得更优的解决方案

if ( required <= workers )
     hi = x;

如果 x 是解决方案，那么我需要 required 个小于或等于 workers 的工人，所以我会尝试通过降低分配给 worker.To 的最大文件夹数的值执行此操作将范围更改为 [lo,x]

 else
lo = x+1;

反之，如果你需要的工人比现有的多，你会把范围扩大到[x+1,hi]

Answer 2

先提取中间函数：

int CountRequiredWorkers(const std::vector<int>& folders, int load) {
    int required = 1, current_load = 0;
    for (int i = 0; i < n; ++i) {
        if (current_load + folders[i] <= x) {
            // the current worker can handle it
            current_load += folders[i];
        } else {
            // assign next worker
            ++required;
            current_load = folders[i];               
        }
    }
    return required;
}

int getMostWork(const vector<int>& folders, int workers) {
    int n = folders.size();
    int lo = *max_element( folders.begin(), folders.end() );
    int hi = accumulate( folders.begin(), folders.end(), 0 );

    while ( lo < hi ) {
      const int mid = lo + (hi-lo)/2;
      const int required = CountRequiredWorkers(mid);

      if (required <= workers)
         hi = mid;
      else
         lo = mid + 1;
    }
    return lo;
}

所以我们对 "virtual" 数组进行二进制搜索，其中索引是总工作量，值是工作人员数。有效索引是从最大的文件夹到所有文件夹的总数。
该数组看起来像 {N, N - 1, N - 1, ..., 2, 2, 1}，我们想要第一个索引 < workers.

看不懂二分查找功能

Can't understand binary search function

c++

binary-search