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 会获胜。

输入格式

两个整数数组 aliceValuesbobValues

输出格式

一个整数,表示Alice赢返回 1,Bob赢返回 -1,平局返回 0。

数据范围

  • $n == aliceValues.length == bobValues.length$
  • $1 <= n <= 10^5$
  • $1 <= aliceValues[i], bobValues[i] <= 100$

输入样例 1:

[1,3]
[2,1]

输出样例 1:

1

输入样例 2:

[1,2]
[3,1]

输出样例 2:

0

输入样例 3:

[2,4,3]
[1,6,7]

输出样例 3:

-1

题目分析

对于Alice来说,她会在两个石子中选择一个对自己更有利的。我们可以通过比较两个石子各自对Alice和Bob的价值差来决定Alice的选择。具体来说:

假设有两个石子 i 和 j,Alice 和 Bob 认为它们的价值分别为 $a_i$, $b_i$ 和 $a_j$, $b_j$。如果 Alice 取了石子 i 而 Bob 取了石子 j,则Alice与Bob的分数差将是 $a_i - b_j$;反之,如果 Alice 取了石子 j 而 Bob 取了石子 i,则分数差将是 $a_j - b_i$。

Alice需要做出的决定取决于这两种情况下分数差的差值,即 $(a_i - b_j) - (a_j - b_i)$,这可以简化为 $(a_i + b_i) - (a_j + b_j)$。当这个值大于 0 时,Alice会优先选择石子 i,而当这个值小于 0 时,Alice会优先选择石子 j。因此,Alice在选择石子时会倾向于选择那些$a_i + b_i$值较大的石子。

代码实现

#define x first 
#define y second
using PII = pair <int,int>;
class Solution {
public:
    int n, sa, sb;
    priority_queue <PII, vector <PII>> heap;
    int stoneGameVI(vector<int>& a, vector<int>& b) {
        n = a.size();
        for(int i = 0; i < n; ++i) heap.push({a[i] + b[i], i});
        while(!heap.empty()) {
            auto t = heap.top(); heap.pop();
            sa += a[t.y];
            if(!heap.empty()) {
                auto p = heap.top(); heap.pop();
                sb += b[p.y];
            }
        }
        if(sa > sb) return 1;
        else if (sa == sb) return 0;
        else return -1;
    }
};
分类: GreedyHeapMathSort

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status