除数(medium)"/>
[二分法]leetcode1283:使结果不超过阈值的最小除数(medium)
题目:
思路:
看到求最大/最小,就先往二分答案上想。
代码如下:
class Solution {
public:// 思路:二分寻找商之和小于等于t的最小除数int smallestDivisor(vector<int>& a, int t) {int l=1,r=*max_element(a.begin(),a.end());while(l<r){int mid=(l+r)>>1,sum=0;for(int x:a)sum+=(x+mid-1)/mid;if(sum<=t)r=mid;// sum<=t,说明初试mid刚好满足情况,则在左区间寻找更小的除数else l=mid+1;// sum>t:说明除数mid太小了,在右区间寻找更大的除数即可}return l;}
};
更多推荐
[二分法]leetcode1283:使结果不超过阈值的最小除数(medium)
发布评论