Bag of Tokens (M)

題目

You have an initial power of P, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).

Your goal is to maximize 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 ith token face up, losing tokens[i] power and gaining 1 score.
If your current score is at least 1, you may play the ith token face down, gaining tokens[i] power and losing 1 score.

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 tokens.

Example 1:

Input: tokens = [100], P = 50
Output: 0
Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.

Example 2:

Input: tokens = [100,200], P = 150
Output: 1
Explanation: Play the 0th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1st token since you cannot play it face up to add to your score.

Example 3:

Input: tokens = [100,200,300,400], P = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
1. Play the 0th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2nd token (300) face up, your power becomes 0 and score becomes 2.

Constraints:

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

題意

給定不同價值的代幣和整數power，有兩種操作：

當power值大于指定代幣的價值時，可以消耗與價值相應的power將該代幣朝上，并獲得1點分數；
當分數大于0時，可以消耗1點分數，將一個代幣朝下，并獲得相應價值的power，

每個代幣僅可被操作一次，求可以得到的最大分數，

思路

貪心演算法：先將代幣按照價值升序排列，從左到右遍歷，如果power足夠，將當前代幣朝上獲得分數；如果power不夠，將最右的代幣朝下轉換成power(只有當最右代幣左邊仍有代幣可操作時)，因為最右的代幣價值最大，保證一定能將之前的代幣朝上，

代碼實作

Java

class Solution {
    public int bagOfTokensScore(int[] tokens, int P) {
        Arrays.sort(tokens);
        int score = 0;
        int left = 0, right = tokens.length - 1;
        while (left <= right) {
            if (P >= tokens[left]) {
                score++;
                P -= tokens[left++];
            } else if (right - left > 1 && score > 0) {
                score--;
                P += tokens[right--];
            } else {
                break;
            }
        }
        return score;
    }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/190085.html

標籤：其他

上一篇：農村的我在1024分享開始杭漂的經歷和心酸，我們一起共勉~

下一篇：0948. Bag of Tokens (M)