0948. Bag of Tokens

题目信息

题号:

0948

难度:

Medium

主题:

令牌、能量与得分、最大得分

原题:

LeetCode 0948

重点:

每个令牌最多使用一次;正面使用消耗能量并增加一分,反面使用消耗一分并增加能量,可随时停止且返回过程中达到的最大得分

题目重述

给定令牌价值数组 tokens 和初始能量 power,初始得分为 0。每个尚未使用的令牌可以选择以下一种方式使用一次:若当前能量至少为其价值,可正面使用,减少对应能量并增加 1 分;若当前得分至少为 1,可反面使用,减少 1 分并增加对应能量。

令牌使用顺序不限,也可以在任意时刻停止。请返回整个过程中能够达到的最高得分,而不是结束时必须保留的得分。

0 <= tokens.length <= 1000,0 <= tokens[i], power <= 10^4。

自建示例

连续正面使用两个较小令牌:

输入:tokens = [50,100,200], power = 150
输出:2
解释:先正面使用 50,能量变为 100、得分为 1;再正面使用 100,能量变为 0、得分为 2。剩余令牌无法让最高得分超过 2。

令牌数组为空:

输入:tokens = [], power = 500
输出:0
解释:没有任何令牌可使用,初始得分 0 就是整个过程中能够达到的最高得分。