数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学在 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、数组 nums 和 k，如下所示：
- sum := 0
- 对于 i 从 0 到 nums 的大小 - 1
- sum := sum + nums[i] / x 的上取整值
- 如果 sum <= k，则返回 true，否则返回 false
- 实际方法如下：
- 设置 low := 1 和 high := 无穷大
- 当 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
更新于：2020年5月2日
621 次浏览
广告