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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
// 1675. Minimize Deviation in Array
#include <stdio.h>
#define SWAP(x, y) (x ^= y ^= x ^= y)
#define MIN(a, b) ((a < b) ? a : b)
/*
* the deviation of the array is the maximum difference between any two elements
* in the array. return minimum deviation the array can have after performing
* 'nums' ops.
*/
void check_larger(int *h, int posi) {
for (int cmp; posi >= 4; posi = cmp) {
cmp = (posi >> 2 << 1) + 1;
if (h[posi] > h[cmp])
SWAP(h[posi], h[cmp]);
else
break;
}
}
void check_smaller(int *h, int posi) {
for (int cmp; posi >= 4; posi = cmp) {
cmp = posi >> 2 << 1;
if (h[posi] < h[cmp])
SWAP(h[posi], h[cmp]);
else
break;
}
}
void insert(int *h, int top, int data) {
h[top] = data;
if (!(top & 1)) {
if (h[top] > h[top >> 1])
check_larger(h, top);
else
check_smaller(h, top);
} else {
if (h[top] < h[top - 1]) {
SWAP(h[top], h[top - 1]);
check_smaller(h, top - 1);
} else
check_larger(h, top);
}
}
void delete_max(int *h, int *top) {
h[3] = h[(*top)--];
int par = 3, chi = 5;
while (chi <= (*top)) {
if (chi + 2 <= (*top) && h[chi + 2] > h[chi])
chi += 2;
if (h[chi] > h[par]) {
SWAP(h[chi], h[par]);
par = chi;
chi = (chi << 1) - 1;
} else
break;
}
if (h[par] < h[par - 1])
SWAP(h[par], h[par - 1]);
}
int minimumDeviation(int *nums, int numsSize) {
int h[numsSize + 2], top = 1, ans;
for (int i = 0; i < numsSize; i++) {
if (nums[i] & 1)
nums[i] <<= 1;
insert(h, ++top, nums[i]);
}
ans = h[3] - h[2];
while (!(h[3] & 1)) {
int t = h[3] >> 1;
delete_max(h, &top);
insert(h, ++top, t);
ans = MIN(ans, h[3] - h[2]);
}
return ans;
}
int main() {
int n1[] = {1, 2, 3, 4}, n2[] = {4, 1, 5, 20, 3}, n3[] = {2, 10, 8};
printf("%d\n", minimumDeviation(n1, 4)); // expect: 1
printf("%d\n", minimumDeviation(n2, 5)); // expect: 3
printf("%d\n", minimumDeviation(n3, 3)); // expect: 3
}
|