Question

1686. Stone Game VI

中文文档

Description

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones in a pile. On each player's turn, they can remove a stone from the pile and receive points based on the stone's value. Alice and Bob may value the stones differently.

You are given two integer arrays of length n, aliceValues and bobValues. Each aliceValues[i] and bobValues[i] represents how Alice and Bob, respectively, value the ith stone.

The winner is the person with the most points after all the stones are chosen. If both players have the same amount of points, the game results in a draw. Both players will play optimally. Both players know the other's values.

Determine the result of the game, and:

• If Alice wins, return 1.
• If Bob wins, return -1.
• If the game results in a draw, return 0.

 

Example 1:

Input: aliceValues = [1,3], bobValues = [2,1]
Output: 1
Explanation:
If Alice takes stone 1 (0-indexed) first, Alice will receive 3 points.
Bob can only choose stone 0, and will only receive 2 points.
Alice wins.

Example 2:

Input: aliceValues = [1,2], bobValues = [3,1]
Output: 0
Explanation:
If Alice takes stone 0, and Bob takes stone 1, they will both have 1 point.
Draw.

Example 3:

Input: aliceValues = [2,4,3], bobValues = [1,6,7]
Output: -1
Explanation:
Regardless of how Alice plays, Bob will be able to have more points than Alice.
For example, if Alice takes stone 1, Bob can take stone 2, and Alice takes stone 0, Alice will have 6 points to Bob's 7.
Bob wins.

 

Constraints:

• n == aliceValues.length == bobValues.length
• 1 <= n <= 105
• 1 <= aliceValues[i], bobValues[i] <= 100

Solutions

Solution 1: Greedy + Sorting

The optimal strategy for picking stones is to maximize one's own score while making the opponent lose as much as possible. Therefore, we create an array $vals$, where $vals[i] = (aliceValues[i] + bobValues[i], i)$ represents the total value and index of the $i$-th stone. Then we sort $vals$ in descending order by total value.

Next, we let Alice and Bob pick stones alternately according to the order of $vals$. Alice picks the stones at even positions in $vals$, and Bob picks the stones at odd positions in $vals$. Finally, we compare the scores of Alice and Bob and return the corresponding result.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the length of the arrays aliceValues and bobValues.

class Solution:
  def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
    vals = [(a + b, i) for i, (a, b) in enumerate(zip(aliceValues, bobValues))]
    vals.sort(reverse=True)
    a = sum(aliceValues[i] for _, i in vals[::2])
    b = sum(bobValues[i] for _, i in vals[1::2])
    if a > b:
      return 1
    if a < b:
      return -1
    return 0

class Solution {
  public int stoneGameVI(int[] aliceValues, int[] bobValues) {
    int n = aliceValues.length;
    int[][] vals = new int[n][0];
    for (int i = 0; i < n; ++i) {
      vals[i] = new int[] {aliceValues[i] + bobValues[i], i};
    }
    Arrays.sort(vals, (a, b) -> b[0] - a[0]);
    int a = 0, b = 0;
    for (int k = 0; k < n; ++k) {
      int i = vals[k][1];
      if (k % 2 == 0) {
        a += aliceValues[i];
      } else {
        b += bobValues[i];
      }
    }
    if (a == b) {
      return 0;
    }
    return a > b ? 1 : -1;
  }
}

class Solution {
public:
  int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
    vector<pair<int, int>> vals;
    int n = aliceValues.size();
    for (int i = 0; i < n; ++i) {
      vals.emplace_back(aliceValues[i] + bobValues[i], i);
    }
    sort(vals.rbegin(), vals.rend());
    int a = 0, b = 0;
    for (int k = 0; k < n; ++k) {
      int i = vals[k].second;
      if (k % 2 == 0) {
        a += aliceValues[i];
      } else {
        b += bobValues[i];
      }
    }
    if (a == b) {
      return 0;
    }
    return a > b ? 1 : -1;
  }
};

func stoneGameVI(aliceValues []int, bobValues []int) int {
  vals := make([][2]int, len(aliceValues))
  for i, a := range aliceValues {
    vals[i] = [2]int{a + bobValues[i], i}
  }
  slices.SortFunc(vals, func(a, b [2]int) int { return b[0] - a[0] })
  a, b := 0, 0
  for k, v := range vals {
    i := v[1]
    if k%2 == 0 {
      a += aliceValues[i]
    } else {
      b += bobValues[i]
    }
  }
  if a > b {
    return 1
  }
  if a < b {
    return -1
  }
  return 0
}

function stoneGameVI(aliceValues: number[], bobValues: number[]): number {
  const n = aliceValues.length;
  const vals: number[][] = [];
  for (let i = 0; i < n; ++i) {
    vals.push([aliceValues[i] + bobValues[i], i]);
  }
  vals.sort((a, b) => b[0] - a[0]);
  let [a, b] = [0, 0];
  for (let k = 0; k < n; ++k) {
    const i = vals[k][1];
    if (k % 2 == 0) {
      a += aliceValues[i];
    } else {
      b += bobValues[i];
    }
  }
  if (a === b) {
    return 0;
  }
  return a > b ? 1 : -1;
}