零，题目描述

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].
Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example 1:

  1. Input: [[10,20],[30,200],[400,50],[30,20]]
  2. Output: 110
  3. Explanation: 
  4. The first person goes to city A for a cost of 10.
  5. The second person goes to city A for a cost of 30.
  6. The third person goes to city B for a cost of 50.
  7. The fourth person goes to city B for a cost of 20.
  8. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Note:

  1. 1 <= costs.length <= 100
  2. It is guaranteed that costs.length is even.
  3. 1 <= costs[i][0], costs[i][1] <= 1000

有一波人，要去A城市或者B城市，给定每个人分别去往两城市的花费。求问怎么样分配去往A城市和B城市的人。
使得总花费最少且每个城市正好有一半的人去。

一，问题分析

这道题是目前为止，我唯一没有能够做出来的easy难度题目。
到现在我还没能完全想清楚。
一种看似直观的想法是，对于每个人计算一个差值。比如说

[[10,20],[30,200],[400,50],[30,20]]

差值计算结果为
[[-10],[-170],[350],[10]]

排序差值计算结果
[[-170],[-10],[10],[350]]

前一半的人去往A市，后一半的人去B市。

某个人的差值意味着，该人去往A市比去往B市多花的钱。负的表示少花费的钱。
证明解释如下
image.png