diff options
Diffstat (limited to 'bag_of_tokens.c')
-rw-r--r-- | bag_of_tokens.c | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/bag_of_tokens.c b/bag_of_tokens.c new file mode 100644 index 0000000..2c26f82 --- /dev/null +++ b/bag_of_tokens.c @@ -0,0 +1,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 +} |