aboutsummaryrefslogtreecommitdiff
path: root/bag_of_tokens.c
diff options
context:
space:
mode:
Diffstat (limited to 'bag_of_tokens.c')
-rw-r--r--bag_of_tokens.c45
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
+}