题解#两地调度#

'''
解题思路：
公司首先将这 2N2N 个人全都安排飞往 BB 市，再选出 NN 个人改变它们的行程，让他们飞往 AA 市。
如果选择改变一个人的行程，那么公司将会额外付出 price_A - price_B 的费用，这个费用可正可负
最优的方案是，选出 price_A - price_B 最小的 NN 个人，让他们飞往 A 市，其余人飞往 B 市。
'''

class Solution:
    def twoCitySchedCost(self, costs: List[List[int]]) -> int:

        n = len(costs)
        #print(costs)

        s = 0
        dis = []
        for i in range(n):
            s += costs[i][0]
            dis.append(costs[i][0] - costs[i][1])
        #print(s)        

        dis = sorted(dis, reverse=1)
        #print(dis)

        s -= sum(dis[:n//2])
        #print(s)  

        return s

costs = [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
t = Solution().twoCitySchedCost(costs)
print(t)