题解#令牌放置#

'''
1、双指针，先对tokens从小到大排序，当power足够时从小到大换取得分(S++)，power不够时由大到小兑换一次(S--)，过程中取得分最大值
2、本题边界及退出条件相对复杂
'''

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:

        T = tokens
        n = len(T)
        p = power        
        T = sorted(T)        
        print(T)

        i = 0
        j = n-1
        s = 0
        res = 0

        while i<=j:

           # 每次尽可能多的兑换得分（S++）
            while 0<=i<=n-1 and i<=j and p>=T[i]:
                p -= T[i]
                i += 1
                s += 1
                print('p=',p,'i=',i,'s=',s)

            if s>res:
                res = s

            # 每次只减少一次(S--)
            if 0<=j<=n-1 and i<=j and s>0 :
                p += T[j]
                j -= 1
                s -= 1
                print('p=',p,'j=',j,'s=',s)

            if 0<=i<=n-1 and p<T[i]:
                break

        print(res)
        return res

#tokens = [100,200,300,400]
#power = 200    # 2
#tokens = [100,200]
#power = 150    # 1
#tokens = [100]
#power = 50    # 0
#tokens = [58,91]
#power = 50    # 0
#tokens = [26]
#power = 51    # 1
tokens = [33,4,28,24,96]
power = 35   # 3
t = Solution().bagOfTokensScore(tokens, power)
print(t)