diff options
Diffstat (limited to 'house_robber4.c')
-rw-r--r-- | house_robber4.c | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/house_robber4.c b/house_robber4.c new file mode 100644 index 0000000..2e1c6e3 --- /dev/null +++ b/house_robber4.c @@ -0,0 +1,36 @@ +// 2560. House Robber IV +#include "leetcode.h" + +/* + * there are several consecutive houses along a street, each of which has some + * money inside. there is also a robber, who wants to steal money from the + * homes, but he refuses to steal from adjacent homes. the capability of the + * robber is the maximum amount of money he steals from one house of all the + * houses he robbed. you are given an integer array 'nums' representing how much + * money is stahsed in each house. more formally, the i'th house from the left + * has 'nums[i]' dollars. you are also given an integer 'k', representing the + * minimum number of houses the robber will steal from. it is always possible to + * steal at least 'k' houses. return the minimum possible capability of the + * robber out of all the possible ways to steal at least 'k' houses. + */ + +int minCapability(int *nums, int numsSize, int k) { + int left = 1, right = 1e9; + while (left < right) { + int mid = (left + right) / 2, take = 0; + for (int i = 0; i < numsSize; i++) + if (nums[i] <= mid) + take++, i++; + if (take >= k) + right = mid; + else + left = mid + 1; + } + return left; +} + +int main() { + int n1[] = {2, 3, 5, 9}, n2[] = {2, 7, 9, 3, 1}; + printf("%d\n", minCapability(n1, ARRAY_SIZE(n1), 2)); // expect: 5 + printf("%d\n", minCapability(n2, ARRAY_SIZE(n2), 2)); // expect: 2 +} |