文章目錄

• • 題目分析
  • 題目鏈接

題目分析

博弈論：最壞情況下求最好。

按$a[i]+b[i]$ 從大到小排序

解釋：
（博弈論）每個人最優(yōu)的選擇都是 要求$自己的?對手的$ 之差 最大。直觀理解就是， 每次選擇的物品使 我得到的價值和 對方損失的價值之和最大！舉個例子，我和對手每人只能選擇1個東西，站在我的立場，如果選擇1號，我得到6塊錢，對方損失1塊錢；選擇2號，我得到4塊，對方損失4塊。 請問我該選1號還是2號? 當然該選擇2號。 如果選擇1號， 我得到6，對方損失1，別看比選擇2號表面多賺2塊錢，可是敵人損失的少了啊！我的滿意度是6+1 =7塊錢 . 而選擇2號，我得到 4塊，對方損失4塊，我的滿意度是4+4 =8塊錢。 這種博弈的結(jié)果就是：選擇兩者各自認為價值之和最大的！才是最優(yōu)決策。

或者直接以本題的石子為例：

如果有2個石子

Alice的價位：a1, a2 Bob的價位: b1, b2

如果 Alice選擇了a1，則Bob只能選 b2 ，此時分差 a1 -b2；

或者 Alice選擇 a2，則Bob選擇b1,此時分差 a2 - b1。

那么這兩種方案對于Alice來說哪一種更優(yōu)，就取決于兩個方案的價值差的比較

.如果a1 -b2 ≥a2 - b1，代表Alice賺。 移項之后等價于 a1+b2 ≥ a2+b2 。

我們可以看到，看誰能贏需要看兩個人對應(yīng)偏好之和。每次取偏好之和最大的，這樣就能判斷誰能贏。

所以貪心策略是:將兩組石頭的價值合并，每次取價值最大的一組。

注：這里不是證明，證明還需要嚴格的數(shù)學(xué)歸納法！

ac代碼

class Solution { public:int stoneGameVI(vector<int>& a, vector<int>& b) {vector<vector<int>> c; // c里面存 兩者之和， a[i] ,b[i] 三個東西int res1=0,res2=0; //兩個人得分之和for(int i=0;i<a.size();i++)c.push_back({a[i]+b[i],a[i],b[i]});sort(c.begin(),c.end());// 從小到大排序，下面則反向遍歷//從大到小遍歷bool flag = true ; //flag ==true 表示 Alice拿 flag ==false 表示Bob拿for(int i= c.size()-1; i>=0; i -- ){if(flag) res1 += c[i][1];elseres2 += c[i][2];flag= !flag;}if(res1>res2) return 1;else if(res1==res2) return 0;return -1;} };

題目鏈接

Leetcode1686. 石子游戲 VI

總結(jié)

以上是生活随笔為你收集整理的Leetcode1686. 石子游戏 VI[C++题解]：博弈论、按照a+b贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。