自动搬运

查看原文

来自洛谷，原作者为

	Asuka二号机 null?

搬运于2025-08-24 21:49:11，当前版本为作者最后更新于2019-08-05 12:53:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

做法看隔壁 我来证结论（撸袖子）

从小学奥数我们可以知道这个轮廓线必然是个正好能包括所有点的矩形，而挪动一个点可以几何地看做对直线y=x作对称。

结论：把所有点翻到y=x一边去是最优的

定义最左点：决定矩形左边界的点，即min(xi)（1<=i<=n）其他类似。

第一种情况长这个样子

这个很显然，红色边界那边翻折一波。

无论你怎么瞎翻，各个边界都不会变大，周长也不会变大。甚至最上点和最左点可能会改变，决策就比较优。

第二种情况

上图：

浅灰色部分是原矩阵，深灰色部分是选择折叠的部分，不妨假设左下角到y=x的距离<右下角到y=x的距离（如果不是的话就下面的部分翻上去 都是一样的）所以显然红色框内就是新的矩阵的最差情况。

显然最左点必然改变（好事情），最上点可能改变（变了就赚 不变不亏）最下点可能改变（变了可能会亏）最右点必然不变

——最差情况，意思就是原来的最左点现在折下去变成了最下点，且最上点没有改变。

但是即使是这样的情况，也可以看出来周长没有发生改变，具体的已经标出来了，同一颜色圈圈里的边互相对应。

那么这样改变之后还有一定的可能性最上点下移，这样就比较优。

那就证明了这么搞不会更劣，那为什么这么搞就是最优的呢？

答：实际上是这样的，可以先考虑单个点的决策——与这个单点在直线同一侧的其他点都可以不看，这和上面的过程是一样的。那么这个单点可能会影响答案，可能不会，但是这样改变后必然不会更不优。然后问题就变成了下一个单点，显然这个单点也可以这么操作。这样下去，把同侧的所有点都翻过来就成了必然的最优决策。

但是电脑不长眼睛，解决 假设左下角到y=x的距离<右下角到y=x的距离 本来是可以直接算的，但是考虑到重量需要处理，所以翻上去翻下去跑两次即可。

在搞重量之前扫一遍，那些挪不挪都无所谓的点，就不用挪了，放回去就行。