在C ++中找到给定阈值的最小除数

假设我们有一个称为nums的整数数组和一个整数k（即阈值），我们将选择一个正整数除数，然后将所有数组除以该整数并将除法的结果求和。我们必须找到最小的除数，使得上述结果小于或等于阈值k。例如-如果nums = [1,2,5,9]且k = 6，则输出将为5。当除数为1时，我们的总和为（1 + 2 + 5 + 9）= 17。如果除数为4，那么我们可以将7作为（1 + 1 + 2 + 3），当除数为5时，总和为（1 + 1 + 1 + 2）= 5

保证会有答案。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为check的方法，它将采用x，array nums和k之类的三个参数，如下所示-

• 和：= 0

• 对于0到nums大小范围内的i – 1

• sum：= sum + nums [i] / x的最大值

• 如果sum <= k，则返回true，否则返回false

• 实际方法如下所示-

• 设置低：= 1和高：= inf

• 从低到高

• 中：=低+（高–低）/ 2

• 如果check(mid,nums,k)，则高：=中，否则低：=中+ 1

• 高回报

• 让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(int x, vector <int> &nums, int th){
      int sum = 0;
      for(int i = 0; i < nums.size(); i++){
         sum += ceil((double)nums[i]/(double)x);
      }
      return sum<=th;
   }
   int smallestDivisor(vector<int>& nums, int th) {
      int low = 1;
      int high = 1e7;
      while(low < high){
         int mid = low + (high - low)/2;
         if(ok(mid, nums, th)){
            high = mid;
         }else low = mid + 1;
      }
      return high;
   }
};
main(){
   vector<int> v = {1,2,5,9};
   Solution ob;
   cout << (ob.smallestDivisor(v, 6));
}

输入值

[1,2,5,9]
6

输出结果

5