在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，arraynums和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