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
}
|