在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

以上是 在C ++中找到给定阈值的最小除数 的全部内容, 来源链接: utcz.com/z/322543.html

回到顶部