【题解】二分答案+贪心-1

1.爱吃香蕉的珂珂

题目链接：爱吃香蕉的珂珂

解题思路：二分答案+贪心

代码如下：

class Solution {
public:
    int minEatingSpeed(vector<int>& p, int h) {
        //check：以一小时k根的速度，吃h个小时，能不能吃完所有的香蕉
        auto check = [&](int speed)->bool{
            int sum = 0;
            for(int e : p){
                sum += (e+speed-1) / speed;
            }
            return sum <= h;//当前时间足够用了
        };
        int l=1, r=*max_element(p.begin(), p.end());
        while(l < r){
            int mid = l + (r-l)/2;
            if(check(mid)) r = mid;
            else l = mid+1;
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.两球之间的磁力

两球之间的磁力

解题思路：二分答案+链接

代码如下：

class Solution {
public:
    int maxDistance(vector<int>& p, int m) {
        //检查以k为最小间距，空篮子里能否放下m个小球
        int n=p.size();
        auto check = [&](int k)->bool{
            int pre=p[0], cnt=1;
            for(int i=1; i<n; ++i){
                if(p[i]-pre >= k){
                    pre=p[i];
                    cnt+=1;
                }
            }
            return cnt>=m;
        };
        sort(p.begin(), p.end());
        //l是下限最小磁力，r是上限最小磁力
        int l=1, r=p.back()-p[0], ans=-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(check(mid)) {
                ans=mid;
                l=mid+1;
            }else r=mid-1;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3.打家劫舍 IV

打家劫舍 IV

代码如下：

class Solution {
public:
//二分
    int minCapability(vector<int>& nums, int k) {
        int n = nums.size();//size返回无符号整型
        int l=0, r=*max_element(nums.begin(), nums.end());
        while(l < r){
            int mid = l + (r - l) /2;
            int count = 0;
            for(int i=0, j=-2; i<n; ++i){//j:上一次小偷的位置
                if(i-j>1 && nums[i]<=mid){//i-j>1:保证房屋不相邻
                    count++;
                    j=i;//更新上一次的位置
                }
            }
            if(count >= k) r = mid;
            else l=mid+1;
        }
        return l;
    } 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.最小化数组中的最大值

最小化数组中的最大值

代码如下：

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        int n = nums.size(), l=0, r=*max_element(nums.begin(), nums.end());
        auto check = [&](int k)->bool{
            long long sum = nums.back();
            for(int i=n-1; i>0; --i){
                if(k < sum){
                    sum = sum - k + nums[i-1];
                }else{
                    sum = nums[i-1];
                }
            }
            return sum<=k;
        };
        //check判断每一次走的贪心是否符合条件
        while(l < r){
            int mid = l + (r - l) / 2;
            if(check(mid)) r = mid;
            else l = mid+1;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int minimizeArrayValue(vector<int>& nums) {
        long long sum=nums[0], ans=nums[0];
        for(int i=1; i<nums.size();++i){
            sum += nums[i];
            ans = max(ans, (sum+i)/(i+1));
        }
        return ans;
    }
};

//a/b向上取整：（a+b-1）/ b
1
2
3
4
5
6
7
8
9
10
11
12
13