力扣1283.使结果不超过阈值的最小除数
力扣1283.使结果不超过阈值的最小除数
题目解析及思路
题目要求找到一个最小的除数,使得数组中每一个数除以这个除数的结果之和<=阈值threshold
-
二分答案
- check一下符合不符合要求
代码
class Solution {
int check(vector<int> nums,int div)
{
int res=0;
for(auto &v:nums)
{
res += (v - 1)/div + 1;
}
return res;
}
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int n = nums.size();
sort(nums.begin(),nums.end());
int l = 1,r = nums[n-1];
while(l < r)
{
int mid = l + r >> 1;
if(check(nums,mid) > threshold) l = mid + 1;
else r = mid;
}
return l;
}
};
原文地址:https://blog.csdn.net/Pisasama/article/details/143088602
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!