在 C++ 中给定阈值查找最小除数
c++server side programmingprogramming更新于 2025/4/15 6:07:17
假设我们有一个名为 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、数组 nums 和 k，如下所示 −
- sum := 0
- for i in range 0 to size of nums – 1
- sum := sum + nums[i] / x 的上限值
- 如果 sum <= k，则返回 true，否则返回 false
- 实际方法将如下所示 −
- 设置 low := 1 和 high := inf
- 当 low < high
- mid := low + (high – low)/2
- 如果 check(mid, nums, k)，则 high := mid，否则 low := mid + 1
- 返回 high
- 让我们看看以下实现以获得更好的理解 −
示例
#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
