小李飞刀:做题第十二弹!

写在前面

今天没有叨逼叨…但是又一次错过了竞赛…
爱睡觉的小李…下周要上班,下下周一定要参加了(握拳

认真做题的分割线

第一题

1029. 两地调度
公司计划面试2N人。第i人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costsi
返回将每个人都飞到某座城市的最低费用,要求每个城市都有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], costsi <= 1000

我的题解:

class Solution(object):
def twoCitySchedCost(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
costs = sorted(costs,key = lambda x:abs(x[0] - x[1]))
costs = costs[::-1]
a,b = 0,0
n = len(costs) //2
res = 0
for i in costs:
if a < n and b < n:
if i[0] < i[1]:
a += 1
res += i[0]
else:
b += 1
res += i[1]
elif a<n:
a += 1
res += i[0]
else:
b += 1
res += i[1]

return res

我的思路:
参考了小江同学的思路(她的blog还在小黑屋…后续补上链接)和这位同学的思路。

  1. 先判断每个人去往两地的成本差,成本差越大的同学要越早被安排的明明白白
  2. 然后分配人员,先分配满n个人的组不再加人,其他的都去另一个组