aboutsummaryrefslogtreecommitdiff
path: root/bag_of_tokens.c
blob: 2c26f827d1cd044d89a9668a45303c81ea53a0e9 (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
// 948. Bag of Tokens
#include "leetcode.h"

/*
 * you have an initial power of 'power', an initial score of 0, and a bag of
 * 'tokens' where 'tokens[i]' is the value of the i'th token (0-indexed). your
 * goal is to maximise your total score by potentially playing each token in one
 * of two ways: -if your current power is at least 'tokens[i]', you may play the
 * i'th token face up, losing 'tokens[i]' power and gaining one score
 * - if your current score is at least one, you may play the i'th token face
 * down, gaining 'tokens[i]' power and losing score 1 each token may be played
 * at most once and in any order. you do not have to play all the tokens. return
 * the largest possible score you can achieve after playing any number of token.
 */

int cmp(const void *a, const void *b) {
  return *(const int *)a - *(const int *)b;
}

int bagOfTokensScore(int *tokens, int tokens_size, int power) {
  if (!tokens_size)
    return 0;
  qsort(tokens, tokens_size, sizeof(int), cmp);
  int left = 0, right = tokens_size - 1, cnt = 0;
  while (left < right) {
    if (tokens[left] <= power) {
      power -= tokens[left++];
      cnt++;
    } else {
      if (!cnt)
        break;
      power += tokens[right--];
      cnt--;
    }
  }
  if (tokens[left] <= power)
    cnt++;
  return cnt;
}

int main() {
  int t1[] = {100}, t2[] = {100, 200};
  printf("%d\n", bagOfTokensScore(t1, 1, 50));  // expect: 0
  printf("%d\n", bagOfTokensScore(t2, 2, 200)); // expect: 2
}