948. Bag of Tokens

题解

这道题目的token是随便选的，所以从该细节推测出来，这道题不应该是个动态规划。
感觉像是个双指针或者贪心的思路。
我们先把所有token排序，然后尽可能的从左到右获取更多的分数。
当没有分数的时候，我们就用1分从最右端换取分数，再进行上述的步骤。
直到两个指针相遇，或者买不起最左端的token停止。

思考

问：这个循环的判断条件，为什么可以改成l < n && power >= tokens[l]？
答：因为当l > r的时候，if判断条件走不进去，无法进行power的补给，所以不满足power >= tokens[i]。

代码

  1. class Solution {
  2. public:
  3.     int bagOfTokensScore(vector<int>& tokens, int power) {
  4.         sort(tokens.begin(), tokens.end());
  5.         int n = tokens.size();
  6.         int l = 0, r = tokens.size() - 1;
  7.         int res = 0;
  8.         while(l <= r && power >= tokens[l]) {
  9.             power -= tokens[l ++];
  10.             res ++;
  11.             if (res && r > l && power < tokens[l]) {
  12.                 power += tokens[r --];
  13.                 res --;
  14.             }
  15.         }
  16.         return res;
  17.     }
  18. };