Codeforces Round #706 Diamond Miner 贪心

题意

有n个点，位于x轴上。又有n个点，位于y轴上。现在让把x轴和y轴的点两两配对，配对的花费为两点间几何距离。求最小可能的花费。

题解

水题。贪心。绝对值小的优先相互配对。

很容易证明：

假设有以下4个点：(x,0)、(x+a,0)、(0,y)、(0,y+b)。其中x、y、a、b均大于0。不难证明，[(x,0),(0,y)] [(x+a,0),(0,y+b)]比[(x+a,0),(0,y)] [(x,0),(0,y+b)]的值更小。

那么对于任意一种非最优的组合，可以做如下优化：选取两点。并对这两点应用上述结论看是否需要调换。然后不断调换的结果就是最优解。

代码：