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)]的值更小。

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

代码:

Submission #109859508 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论