LeetCode/2560. House Robber IV.cpp at main · theahmedhany/LeetCode · GitHub

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
29
30
31
32
33
34
35
// 2560. House Robber IV : https://leetcode.com/problems/house-robber-iv/

class Solution {
    public:
        bool ok(int c, vector<int>& nums, int k) {
            int cnt = 0;

            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] <= c) {
                    cnt++;
                    i++;
                }
            }

            return cnt >= k;
        }

        int minCapability(vector<int>& nums, int k) {
            int st = *min_element(nums.begin(), nums.end()),
                ed = *max_element(nums.begin(), nums.end()), cur = -1, md;

            while (st <= ed) {
                md = (st + ed) / 2;

                if (ok(md, nums, k)) {
                    cur = md;
                    ed = md - 1;
                } else {
                    st = md + 1;
                }
            }

            return cur;
        }
    };