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

1.准时到达的列车最小时速

题目链接：准时到达的列车最小时速

代码如下：

class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int l=1, r = 1e7, n = dist.size();
        long long hr = llround(hour*100);
        if(hr <= (n-1) * 100) return -1;
        auto check = [&](int mid)->bool{
            long long t = 0;//前n-1段的时间
            for(int i=0; i<n-1; ++i){
                t += (dist[i] + mid - 1) / mid;
            }
            t *= mid;
            t += dist[n-1];
            return (t*100 <= hr*mid);
        };

        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
21
22
23
24

2.每个小孩最多能分到多少糖果

题目链接：每个小孩最多能分到多少糖果

代码如下：

class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        int l = 1, r = *max_element(candies.begin(), candies.end());
        int n = candies.size();
        //检查每个小孩分到i个糖果是否可以满足要求
        auto check = [&](int mid)->bool{
            long long res = 0;
            for(int i=0; i<n; ++i){
                res += candies[i] / mid;
            }
            return res >= k;
        };
        while(l <= r){
            int mid = l + (r-l)/2;
            if(check(mid)) l = mid+1;
            else r = mid-1;
        }
        return l-1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.完成旅途的最少时间

题目链接：完成旅途的最少时间

代码如下：

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long l=1;
        long long r = (long long)totalTrips*(*max_element(time.begin(), time.end()));
        int n = time.size();
        auto check = [&](long long k)->bool{
            long long res = 0;
            for(int i=0; i<n; ++i){
                res += k/time[i];
            }
            return res >= totalTrips;
        };
        while(l < r) {
            long long 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
21

4.礼盒的最大甜蜜度

题目链接：礼盒的最大甜蜜度

代码如下：

class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        int n = price.size();
        sort(price.begin(), price.end());
        int l=0, r=price[n-1] - price[0];
        //检查mid的甜蜜度是否可以被满足
        auto check = [&](int mid)->bool{
            int cnt = 0, pre = INT_MIN >> 1;
            for(int p : price){
                if(p - pre >= mid){
                    cnt++;
                    pre = p;
                }
            }
            return cnt >= k;
        };
        while(l < r){
            int mid = (l+r+1)/2;
            if(check(mid)) l=mid;
            else r=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
22
23
24
25

这两篇的二分答案和贪心都是同一类型，可以放在一起做