一、題目要求
- Alice 和 Bob 輪流玩一個游戲，Alice 先手，一堆石子里總共有 n 個石子，輪到某個玩家時，他可以移出一個石子并得到這個石子的價值，Alice 和 Bob 對石子價值有不一樣的的評判標準，雙方都知道對方的評判標準，
- 給你兩個長度為 n 的整數陣列 aliceValues 和 bobValues，aliceValues[i] 和 bobValues[i] 分別表示 Alice 和 Bob 認為第 i 個石子的價值，
- 所有石子都被取完后，得分較高的人為勝者，如果兩個玩家得分相同，那么為平局，兩位玩家都會采用 最優策略 進行游戲，
- 請你推斷游戲的結果，用如下的方式表示：
-
- 如果 Alice 贏，回傳 1；
-
- 如果 Bob 贏，回傳 -1；
-
- 如果游戲平局，回傳 0，
- 示例 1：
輸入：aliceValues = [1,3], bobValues = [2,1]
輸出：1
解釋：
如果 Alice 拿石子 1 （下標從 0開始），那么 Alice 可以得到 3 分，
Bob 只能選擇石子 0 ，得到 2 分，
Alice 獲勝，
- 示例 2：
輸入：aliceValues = [1,2], bobValues = [3,1]
輸出：0
解釋：
Alice 拿石子 0 ， Bob 拿石子 1 ，他們得分都為 1 分，
打平，
- 示例 3：
輸入：aliceValues = [2,4,3], bobValues = [1,6,7]
輸出：-1
解釋：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分，
比方說，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 會得到 6 分而 Bob 得分為 7 分，
Bob 會獲勝，
二、求解演算法
① 貪心演算法
- 假設只有兩個石頭，對于 a， b 的價值分別是 a1，a2，b1，b2：
-
- 第一種方案是 A 取第一個，B 取第二個，A 與 B 的價值差是 c1 = a1 - b2；
-
- 第二種方案是 A 取第二個，B 取第一個，A 與 B 的價值差是 c2 = a2 - b1；
- 那么這兩種方案對于 A 來說哪一種更優，就取決于兩個方案的價值差的比較，
- 記 c = c1 - c2 = （a1 - b2） - (a2 - b1) = (a1 + b1) - (a2 + b2)，如果 c > 0 那么方案一更優，如果 c == 0，那么兩種方案價值一樣，如果 c < 0 ，那么方案二更優，
- 比較兩個方案的優劣就如同比較 a1 + b1 與 a2 + b2 的優劣，歸納一下就是比較每個下標 i 的 a[i] + b[i] 的優劣，所以貪心的策略：將兩組石頭的價值合并，每次取價值最大的那一組，
- 合并 aliceValues 與 bobValues 的陣列，按最大價值從大到小排列，Alice 先選，Bob 后選，偶數下標就標稱 Alice 選取的石頭的總價值，Bob 選的則是奇數下標的石子，比較兩個總和，
- C++ 示例：
class Solution {
public:
int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
vector<pair<int, int>> mp; // 記錄價值和以及下標
int n = aliceValues.size();
for(int i = 0; i < n; i++) {
int dis = aliceValues[i] + bobValues[i];
mp.emplace_back(dis, i);
}
sort(mp.rbegin(), mp.rend()); // 從大到小排序
int sum1 = 0, sum2 = 0;
for(int i = 0; i < n; i++) {
if(i % 2 == 0) sum1 += aliceValues[mp[i].second];// 偶數下標a來取
else sum2 += bobValues[mp[i].second]; // 奇數下標b來取
}
if(sum1 == sum2) return 0; // 比較結果
else if(sum1 > sum2) return 1;
else return -1;
}
};
② 數學推理
- 雙贏才是贏，不僅 Alice 要認為某塊石頭的價值大，Bob 也要認為的時候，才是真的大，
- 因此，將某塊石頭在 Alice 眼中的價值 +Bob 眼里的價值相加，排序，然后 Alice 和 Bob 依次進行挑選，最比較 Alice 和 Bob 的得分，
- C++ 示例：
class Solution {
public:
int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
vector<pair<int,int>>vc;
int len=aliceValues.size();
for(int i=0;i<len;i++){
// 合并石頭的雙從的價值
int sum=aliceValues[i]+bobValues[i];
vc.push_back({sum,i});
}
// 對合并后的石頭的價值進行排序
sort(vc.rbegin(),vc.rend());
// Alice的得分
int A=0;
// Bob的得分
int B=0;
for(int i=0;i<len;i++){
// 依次輪流拿去石頭
if(i%2==0) {
A+=aliceValues[vc[i].second];
} else {
B+=bobValues[vc[i].second];
}
}
// 回傳最后的結果
if(A==B){
return 0;
}
return A>B?1:-1;
}
};
三、博客之星
- 今年是我第一次參加博客之星，需要各位大佬的支持，麻煩百忙之中，抽出一點寶貴的時間，給我投一下票：https://bbs.csdn.net/topics/603955258 給我一個五星（串列會一一全部回復），不勝感激！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/401486.html
標籤：其他
下一篇：暢玩三子棋（可選擇棋盤大小）