avatar

两地调度,1029问题,参考解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package com.wzl.day21;

import java.util.Arrays;
import java.util.Comparator;

public class Day21 {
//公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。
//
// 返回将每个人都飞到某座城市的最低费用,要求每个城市都有 N 人抵达。
//
//
//
// 示例:
//
// 输入:[[10,20],[30,200],[400,50],[30,20]]
//输出:110
//解释:
//第一个人去 A 市,费用为 10。
//第二个人去 A 市,费用为 30。
//第三个人去 B 市,费用为 50。
//第四个人去 B 市,费用为 20。
//
//最低总费用为 10 + 30 + 50 + 20 = 110,每个城市都有一半的人在面试。
//
//
//
//
// 提示:
//
//
// 1 <= costs.length <= 100
// costs.length 为偶数
// 1 <= costs[i][0], costs[i][1] <= 1000
//
// Related Topics 贪心算法


//leetcode submit region begin(Prohibit modification and deletion)
public int twoCitySchedCost(int[][] costs) {
// Sort by a gain which company has
// by sending a person to city A and not to city B
Arrays.sort(costs, new Comparator<int[]>() {
[@Override](https://my.oschina.net/u/1162528)
public int compare(int[] o1, int[] o2) {
return o1[0] - o1[1] - (o2[0] - o2[1]);
}
});

int total = 0;
int n = costs.length / 2;
// To optimize the company expenses,
// send the first n persons to the city A
// and the others to the city B
for (int i = 0; i < n; ++i) total += costs[i][0] + costs[i + n][1];
return total;
}

//leetcode submit region end(Prohibit modification and deletion)

}
文章作者: 无知的小狼
文章链接: https://bytedance.press/2020/01/09/%E4%B8%A4%E5%9C%B0%E8%B0%83%E5%BA%A6%EF%BC%8C1029%E9%97%AE%E9%A2%98%EF%BC%8C%E5%8F%82%E8%80%83%E8%A7%A3%E7%AD%94/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 无知的小狼

评论