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
36
|
// 3066. Minimum Operations to Exceed Threshold Value II
#include "leetcode.h"
/*
* you are given a 0-indexed integer array 'nums', and an integer 'k'. in one
* operation, you will take the two smallest integers 'x' and 'y' in 'nums',
* remove 'x' and 'y' from 'nums', and add 'min(x, y) * 2 + max(x, y)' anywhere
* in the array. note that you can only apply the described operation if 'nums'
* contains at least two elements. return the minimum number of operations
* needed so that all elements of the array are greater than or equal to 'k'.
*/
int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
int minOperations(int *nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), cmp);
int *arr = (int *)malloc(numsSize * sizeof(int));
for (int i = 0, j = 0, m = 0, cnt = 0, x, y;; ++cnt) {
x = i < numsSize && (j >= m || nums[i] <= arr[j]) ? nums[i++] : arr[j++];
if (x >= k) {
free(arr);
return cnt;
}
y = i < numsSize && (j >= m || nums[i] <= arr[j]) ? nums[i++] : arr[j++];
long tmp = 2L * x + y;
arr[m++] = tmp < k ? (int)tmp : k;
}
free(arr);
return -1;
}
int main() {
int n1[] = {2, 11, 10, 1, 3}, n2[] = {1, 1, 2, 4, 9};
printf("%d\n", minOperations(n1, ARRAY_SIZE(n1), 10)); // expect: 2
printf("%d\n", minOperations(n2, ARRAY_SIZE(n2), 20)); // expect: 4
}
|