Two City Scheduling
这题可有点绕,开始直接想的就是动态规划,然后琢磨了一下,觉得easy应该有greedy的做法,于是想到比较两个人去A和B之间的差的abs,即B[1]-A[1](去B点cost的差)和B[0]-A[0](去A点的cost的差),然后排序,再求和。
最后翻了翻答案, 看到以下解法,真是更巧妙。
举例[[10,20],[30,200],[400,50],[30,20]],因为只有A,B两个点,所以我们假设所有人都去一个点B,那么就是 20 + 200 + 50 + 20. 然后我们数组的两个数相减,得出如果去A,那么哪些人优先去?[20-10], [200-30], [50-400],[20-30] -> [10], [170], [-350], [-10], 然后排序,[170], [10], [-10], [-350]. 这个数组序列是按照最应该去A的人。最后是最巧妙的一点, 我们因为已知n个人要去A,所以只需取前两个,[170], [10].,
然后是我们如何加到最开始的数组? 首先,我们把[170], [10] 还原成 [200-30], [20-10], 然后我们用20 + 200 + 50 + 20 – (200-30) – (20 – 10).就可以消去B并且加回A。
class Solution {
public int twoCitySchedCost(int[][] costs) {
int sum = 0;
for(int[] c : costs)
sum += c[1];
Arrays.sort(costs,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2){
return (o2[1]-o2[0]) - (o1[1]-o1[0]);
}});
for(int i = 0; i < costs.length / 2; i++)
sum -= (costs[i][1] - costs[i][0]);
return sum;
}
}