aboutsummaryrefslogtreecommitdiff
path: root/maximal_score_apply_k_operation.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-13 18:33:28 -0600
committerJack Sangdahl <[email protected]>2024-10-13 18:33:28 -0600
commit8b5384e0ae2de4fa883e2b69d93267db48d2e095 (patch)
tree0e9031938b9f9e83f17008ab7d9359d0f0b19bb6 /maximal_score_apply_k_operation.c
parent0f3e9ac36b523a36c78981c031f2967e9d878136 (diff)
downloadleetcode-8b5384e0ae2de4fa883e2b69d93267db48d2e095.tar.gz
leetcode-8b5384e0ae2de4fa883e2b69d93267db48d2e095.zip
2530. maximal score after applying k operations
Diffstat (limited to 'maximal_score_apply_k_operation.c')
-rw-r--r--maximal_score_apply_k_operation.c53
1 files changed, 53 insertions, 0 deletions
diff --git a/maximal_score_apply_k_operation.c b/maximal_score_apply_k_operation.c
new file mode 100644
index 0000000..5619fd8
--- /dev/null
+++ b/maximal_score_apply_k_operation.c
@@ -0,0 +1,53 @@
+// 2530. Maximal Score After Applying K Operations
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums' and an integer 'k'. you have a
+ * starting score of 0. in one operation you can choose an index 'i' such that
+ * '0 <= i < nums.length', increase your score by 'nums[i]', and replace
+ * 'nums[i]' with 'ceil(nums[i] / 3)'. return the maximum possible score you can
+ * attain after applying exactly 'k' operations. the ceiling function
+ * 'ceil(val)' is the least integer greater than or equal to 'val'.
+ */
+
+#define SWAP(x, y) \
+ do { \
+ typeof(x) _x = x; \
+ typeof(y) _y = y; \
+ x = _y; \
+ y = _x; \
+ } while (0)
+
+void heapify(int *arr, int n, int i) {
+ int max = i, l = 2 * i + 1, r = 2 * i + 2;
+ if (l < n && arr[l] > arr[max])
+ max = l;
+ if (r < n && arr[r] > arr[max])
+ max = r;
+ if (max != i) {
+ SWAP(arr[i], arr[max]);
+ heapify(arr, n, max);
+ }
+}
+
+void build_heap(int *arr, int n) {
+ for (int i = (n / 2) - 1; i >= 0; i--)
+ heapify(arr, n, i);
+}
+
+long long maxKelements(int *nums, int numsSize, int k) {
+ long long score = 0;
+ build_heap(nums, numsSize);
+ while (k--) {
+ score += nums[0];
+ nums[0] = ceil(nums[0] / 3.0);
+ heapify(nums, numsSize, 0);
+ }
+ return score;
+}
+
+int main() {
+ int n1[] = {10, 10, 10, 10, 10}, n2[] = {1, 10, 3, 3, 3};
+ printf("%lld\n", maxKelements(n1, ARRAY_SIZE(n1), 5)); // expect: 50
+ printf("%lld\n", maxKelements(n2, ARRAY_SIZE(n2), 3)); // expect: 17
+}