資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的令牌包
假設我們擁有初始能量 P，初始分數為 0 分，以及一個令牌包。現在每個令牌最多隻能使用一次，每個令牌都有一個值 token[i]，並且可能有兩種使用方法：
如果我們至少擁有 token[i] 的能量，我們可以正面朝上放置令牌，損失 token[i] 能量，獲得 1 分。
否則，如果我們至少有 1 分，我們可以反面朝上放置令牌，獲得 token[i] 能量，損失 1 分。
我們需要找到我們可以獲得的最大分數。
例如，如果輸入是 tokens = [100,200,300,400] 和 P = 200，則輸出為 2。
為了解決這個問題，我們將遵循以下步驟：
n := 陣列 v 的大小，ret := 0
對 v 陣列進行排序
設定 i := 0 和 j := n – 1，curr := P
當 i <= j 且 x >= v[i] 時
當 i <= j 且 x >= v[i] 時
x 減去 v[i]，curr 和 i 加 1
ret := curr 和 ret 的最大值
當 j >= i 且 curr 不為 0 且 x < v[i] 時
x 加上 v[j]，curr 和 j 減 1
返回 ret
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int bagOfTokensScore(vector<int>& v, int x) {
int n = v.size();
int ret = 0;
sort(v.begin(), v.end());
int i = 0;
int j = n - 1;
int curr = 0;
while(i <= j && x >= v[i]){
while(i <= j && x >= v[i]){
x -= v[i];
curr++;
i++;
}
ret = max(curr, ret);
while(j >= i && curr && x < v[i]){
curr--;
x += v[j];
j--;
}
}
return ret;
}
};
main(){
vector<int> v1 = {100,200,300,400};
Solution ob;
cout << (ob.bagOfTokensScore(v1, 200));
}輸入
[100,200,300,400] 200
輸出
2
更新於：2020年4月30日
328 次瀏覽
廣告