1029. Two City Scheduling¶
题目信息¶
- 题号:
1029
- 难度:
Medium
- 主题:
人员分配、双城市、最小总费用
- 原题:
- 重点:
输入包含
2n个人,必须恰好安排n人去 A 城、n人去 B 城,并最小化全部出行费用
题目重述¶
给定费用矩阵 costs,其中 costs[i] = [a_i, b_i] 表示第 i 个人前往 A 城和 B 城的费用。总人数为偶数,记为 2n。
必须把每个人安排到且仅安排到一个城市,并保证两个城市各接收恰好 n 人。请返回满足人数约束时所有人的最小总出行费用。
2 <= costs.length <= 100 且长度为偶数,1 <= a_i, b_i <= 1000。
自建示例¶
选择个人费用差异较大的城市:
输入:costs = [[30,70],[80,20],[40,60],[90,10]]
输出:100
解释:安排第 0、2 人去 A 城,费用为 30 + 40;安排第 1、3 人去 B 城,费用为 20 + 10,总费用为 100。
只有两个人:
输入:costs = [[5,100],[7,9]]
输出:14
解释:两个城市各需一人。第 0 人去 A 城花费 5,第 1 人去 B 城花费 9,总费用为 14。