在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