From d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa Mon Sep 17 00:00:00 2001 From: jack <0x6A73@pm.me> Date: Fri, 14 Jun 2024 13:13:15 -0600 Subject: initial --- max_subseq_score.c | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 99 insertions(+) create mode 100644 max_subseq_score.c (limited to 'max_subseq_score.c') diff --git a/max_subseq_score.c b/max_subseq_score.c new file mode 100644 index 0000000..deb41c1 --- /dev/null +++ b/max_subseq_score.c @@ -0,0 +1,99 @@ +// 2542. Maximum Subsequence Score +#include +#include +#include + +/* + * given two 0-indexed integer arrays 'num1' and 'nums2' of equal length 'n' and + * a positive integer 'k'. you must choose a subsequence of indices from 'nums1' + * of length 'k'. for chosen indices 'i0, i1, ..., ik-1', your score is defined + * as + * - the sum of the selected elements from 'nums1' multiplied with the minimum + * of the selected elements from 'nums2' + * - it can defined simply as '(num1[i0] + nums1[i1] + ... + nums1[ik - 1]) * + * min(nums2[i0], nums2[i1], ..., nums2[ik - 1])' return the maximum possible + * score. a subseqnce of indices of an array is a set that can be derived from + * the set '{0, 1, ..., n - 1}' by deleting no elements + */ + +int cmp(const void *a, const void *b) { + int *ptr_a = *(int **)a; + int *ptr_b = *(int **)b; + if (ptr_a[1] == ptr_b[1]) + return ptr_a[0] - ptr_b[0]; + return ptr_a[1] - ptr_b[1]; +} + +int cmp1(const void *a, const void *b) { return *(int *)a - *(int *)b; } + +void insert(int *heap, int k, int val, long long *sum) { + if (val <= heap[0]) + return; + int f = 0; + *sum = *sum + val - heap[0]; + heap[0] = val; + while (1) { + int child1 = 2 * f + 1; + int child2 = 2 * f + 2; + if (child2 < k) { + if (heap[child1] <= heap[child2]) { + if (heap[child1] < heap[f]) { + int tmp = heap[child1]; + heap[child1] = heap[f]; + heap[f] = tmp; + f = child1; + } else + break; + } else { + if (heap[child2] < heap[f]) { + int tmp = heap[child2]; + heap[child2] = heap[f]; + heap[f] = tmp; + f = child2; + } else + break; + } + } else if (child1 < k) { + if (heap[child1] < heap[f]) { + int tmp = heap[child1]; + heap[child1] = heap[f]; + heap[f] = tmp; + f = child1; + } else + break; + } else + break; + } +} + +long long maxScore(int *nums1, int nums1_size, int *nums2, int nums2_size, + int k) { + long long ans = 0, sum = 0; + int n = nums1_size; + int **tmp = malloc(n * sizeof(int *)); + int *heap = malloc(2 * k * sizeof(int)); + for (int i = 0; i < n; i++) { + tmp[i] = malloc(2 * sizeof(int)); + tmp[i][0] = nums1[i]; + tmp[i][1] = nums2[i]; + } + qsort(tmp, n, sizeof(int *), cmp); + for (int i = 0; i < k; i++) { + heap[i] = tmp[n - 1 - i][0]; + sum += tmp[n - 1 - i][0]; + } + ans = sum * (long long)tmp[n - k][1]; + qsort(heap, k, sizeof(int), cmp1); + for (int i = n - k - 1; i >= 0; i--) { + insert(heap, k, tmp[i][0], &sum); + ans = fmax(ans, sum * tmp[i][1]); + } + return ans; +} + +int main() { + int n11[] = {1, 3, 3, 2}, n21[] = {2, 1, 3, 4}; + int n12[] = {4, 2, 3, 1, 1}, n22[] = {7, 5, 10, 9, 6}; + printf("%lld\n", maxScore(n11, 4, n21, 4, 3)); // expect: 12 + printf("%lld\n", maxScore(n12, 5, n22, 5, 1)); // expect: 30 +} -- cgit v1.2.3