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
|
// 135. Candy
#include <stdio.h>
#include <stdlib.h>
/*
* there are 'n' children standing in a line. each child is assigned a rating
* value. given in the integer array 'ratings'. you are giving candies to these
* children subjected to the following requirements
* - each child must have at least one candy
* - children with a higher rating get more candies than their neighbours
* return the maximum number of candies you need to have to distribute the
* candies to the children
*/
int candy(int *ratings, int ratings_size) {
if (!ratings_size)
return 0;
int *a = (int *)malloc(sizeof(int) * ratings_size);
a[0] = 1;
for (int i = 1; i < ratings_size; i++) {
if (ratings[i - 1] < ratings[i])
a[i] = a[i - 1] + 1;
else if (ratings[i - 1] == ratings[i])
a[i] = 1;
else {
int j = i - 1, k = 1, n;
while (j < ratings_size - 1 && ratings[j] > ratings[j + 1])
k++, j++;
if (a[i - 1] >= k) {
n = k - 1;
j = i;
while (j < i + k - 1) {
a[j] = n;
n--;
j++;
}
} else {
n = k;
j = i - 1;
while (j < i + k - 1) {
a[j] = n;
n--;
j++;
}
}
i = j - 1;
}
}
int ans = 0;
for (int i = 0; i < ratings_size; i++)
ans += a[i];
return ans;
}
int main() {
int r1[] = {1, 0, 2}, r2[] = {1, 2, 2};
printf("%d\n", candy(r1, 3)); // expect: 5
printf("%d\n", candy(r2, 3)); // expect: 4
}
|