aboutsummaryrefslogtreecommitdiff
path: root/find_score_arr_mark.c
blob: cb5aecb35e5250218e79b4fa51a8661e09b14cb2 (plain)
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
}