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
|
// 2593. Find Score of an Array After Marking All Elements
#include "leetcode.h"
/*
* given an array 'nums' consisting of positive integers. starting with 'score =
* 0', apply the following algorithm
* - choose the smallest integer of the array that is not marked. if there is a
* tie, choose the one with the smallest index
* - add the value of the chosen integer to 'score'
* - mark the chosen element and its two adjacent elements if they exist
* - repeat until all the array elements are marked
* return the score you get after applying the above algorithm
*/
struct pair {
int val;
int idx;
};
int cmp(const void *a, const void *b) {
const struct pair p_a = *(const struct pair *)a;
const struct pair p_b = *(const struct pair *)b;
if (p_a.val == p_b.val)
return p_a.idx - p_b.idx;
return p_a.val - p_b.val;
}
long long findScore(int *nums, int nums_size) {
if (nums_size == 1)
return (long long)nums[0];
struct pair *arr = (struct pair *)calloc(nums_size, sizeof(struct pair));
bool *is_marked = (bool *)calloc(nums_size, sizeof(bool));
for (int i = 0; i < nums_size; i++) {
arr[i].val = nums[i];
arr[i].idx = i;
}
qsort(arr, nums_size, sizeof(struct pair), cmp);
long long ans = 0;
for (int i = 0; i < nums_size; i++)
if (!is_marked[arr[i].idx]) {
ans += arr[i].val;
if (arr[i].idx + 1 < nums_size)
is_marked[arr[i].idx + 1] = true;
if (arr[i].idx - 1 >= 0)
is_marked[arr[i].idx - 1] = true;
}
free(arr), free(is_marked);
return ans;
}
int main() {
int n1[] = {2, 1, 3, 4, 5, 2}, n2[] = {2, 3, 5, 1, 3, 2};
printf("%lld\n", findScore(n1, 6)); // expect: 7
printf("%lld\n", findScore(n2, 6)); // expect: 5
}
|