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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
// 2602. Minimum Operations to Make All Array Elements Equal
#include "leetcode.h"
/*
* given an array 'nums' consisting of positive integers. you are also given an
* integer array 'queries' of size 'm'. for the i'th query, you want to make all
* of the elements of 'nums' equal to 'queries[i]'. you can perform the
* following operation on the array any number of times: increase or decrease an
* element of the array by 1. return an array 'ans' of size 'm' where 'ans[i]'
* is the minimum number of operations to make all elements of 'nums' equal to
* 'queries[i]'. note that after each query the array is reset to its original
* state
*/
int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
long long *minOperations(int *nums, int numsSize, int *queries, int queriesSize,
int *returnSize) {
long long *prefix_sum = (long long *)calloc(numsSize + 1, sizeof(long long));
long long *ans = (long long *)calloc(queriesSize, sizeof(long long));
qsort(nums, numsSize, sizeof(int), cmp);
for (int i = 1; i <= numsSize; i++)
prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];
for (int i = 0; i < queriesSize; i++) {
if (queries[i] < nums[0])
ans[i] = prefix_sum[numsSize] - (long long)queries[i] * numsSize;
else if (queries[i] > nums[numsSize - 1])
ans[i] = (long long)queries[i] * numsSize - prefix_sum[numsSize];
else {
int l = 0, r = numsSize - 1, m;
while (l < r) {
m = l + ((r - l) >> 1);
if (nums[m] < queries[i])
l = m + 1;
else
r = m;
}
ans[i] = (long long)queries[i] * (2 * l - numsSize) +
prefix_sum[numsSize] - 2 * prefix_sum[l];
}
}
*returnSize = queriesSize;
return ans;
}
int main() {
int n1[] = {3, 1, 6, 8}, q1[] = {1, 5};
int n2[] = {2, 9, 6, 3}, q2[] = {10};
int rcs1[] = {}, rcs2[] = {};
long long *mo1 = minOperations(n1, ARRAY_SIZE(n1), q1, ARRAY_SIZE(q1), rcs1);
long long *mo2 = minOperations(n2, ARRAY_SIZE(n2), q2, ARRAY_SIZE(q2), rcs2);
for (int i = 0; i < 2; i++)
printf("%lld ", mo1[i]); // expect: 14 10
printf("\n");
for (int i = 0; i < 1; i++)
printf("%lld ", mo2[i]); // expect: 20
printf("\n");
}
|