LeetCode.1686. 石子游戏 VI

题目

题目链接

分析

本题采取贪心的策略
我们先假设只有两个石头a,b，
对于 Alice 价值分别为 a1,a2，
对于 Bob 价值而言价值分别是 b1,b2

1. 第一种方案是 Alice取第一个，Bob 取第二个，Alice与Bob的价值差是 c1 = a1 - b1；
2. 第一种方案是 Alice取第二个，Bob 取第一个，Alice与Bob的价值差是 c1 = a2 - b2；

那么这两种方案对于 Alice来说哪一种更优呢？？
取决于两种方案的价值差，记 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]的优劣。

所以贪心的策略：将两组石头的价值合并，每次取价值最大的那一组。

总结以上：先将两个数组的价值合并，并用下标去标记，对价值进行排序，
Alice取偶数下标，Bob取奇数下标，最后比较Alice和Bob的价值总和。

代码

class Solution {public int stoneGameVI(int[] aliceValues, int[] bobValues) {int n = aliceValues.length;Integer[] ids = new Integer[n];for (int i = 0; i < n; ++i) ids[i] = i;// 两个数组价值之和按照 大->小 排序，ids 记录下标// 例如： aliceValues = {1, 2, 3}; bobValues = {3, 1, 3};// 经过下面的代码：ids = {2,0,1}Arrays.sort(ids, (a, b) -> {int val1 = aliceValues[a] + bobValues[a];int val2 = aliceValues[b] + bobValues[b];return val2 - val1;});// Alice 价值总和int alisCount = 0;// Bob 价值总和int bobCount = 0;for(int i  =0;i < n;i ++) {// 偶数下标，Alice取值if(i % 2 == 0) {alisCount += aliceValues[ids[i]];}else {// 奇数下标，Bob取值bobCount += bobValues[ids[i]];}}if(alisCount - bobCount > 0) {return 1;}else if(alisCount == bobCount) {return 0;}else {return -1;}}
}