_1686.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.PriorityQueue;

publicclass_1686 {
publicstaticclassSolution1 {
/*
 * 1. The most optimal strategy for each player is take the stone with the currently max combined value instead of just his own max value
 * because when they take the stone, it also removes the same stone from the other player, ending the best situation for them;
 * 2. Both players would stick to the above strategy since it's the best for themselves and they are playing optimally.
 */
publicintstoneGameVI(int[] aliceValues, int[] bobValues) {
PriorityQueue<int[]> maxHeap =
newPriorityQueue<>((a, b) -> a[0] - b[0] == 0 ? a[1] - b[1] : b[0] - a[0]);
for (inti = 0; i < aliceValues.length; i++) {
maxHeap.offer(newint[] {aliceValues[i] + bobValues[i], i});
 }
int[] sums = newint[aliceValues.length];
booleanaliceTurn = true;
while (!maxHeap.isEmpty()) {
int[] curr = maxHeap.poll();
if (aliceTurn) {
aliceTurn = false;
sums[curr[1]] = aliceValues[curr[1]];
 } else {
aliceTurn = true;
sums[curr[1]] = -bobValues[curr[1]];
 }
 }
intsum = 0;
for (ints : sums) {
sum += s;
 }
if (sum == 0) {
return0;
 } elseif (sum > 0) {
return1;
 } else {
return -1;
 }
 }
 }
}