二分算法题目合集
| 题目 | 来源 | 难度 |
|---|---|---|
| 袋子里数目最少的球 | 力扣 | 中等 |
| 礼盒的最大甜蜜度 | 力扣 | 中等 |
| 两球之间的磁力 | 力扣 | 中等 |
| 机器人跳跃问题 | Acwing | 中等 |
| 分巧克力 | Acwing | 中等 |
| 分割数组的最大值 | 力扣 | 困难 |
袋子里数目最少的球
class Solution {
public:
int minimumSize(vector<int>& nums, int maxOperations) {
int left = 1, right = *max_element(nums.begin(),nums.end());
while(left < right){
long long ans = 0;
int mid = left + right >> 1;
for(int x:nums) ans += (x-1)/mid;
if(ans <= maxOperations) right = mid;
else left = mid + 1;
}
return left;
}
};
礼物的最大甜蜜度
class Solution {
public:
int maximumTastiness(vector<int>& price, int k) {
sort(price.begin(),price.end());
int l = 0,r = 1e9;
while(l < r){
int mid = l + r + 1 >> 1;
if(check(price,k,mid)) l = mid;
else r = mid - 1;
}
return l;
}
bool check(vector<int> &price,int k,int mid){
int cnt = 1;
int cur = price[0];
for(int i=1;i<price.size();i++){
if(price[i] - cur >= mid){
cnt++;
cur = price[i];
}
}
return cnt >= k;
}
};