FoxAndAvatar

作者：寇煜杭

关键字：搜索

题目简述

给你一个宽度为$w$，无限高的方格。将$1$到$n$从方格第一行第一格从左到右，从上到下依次填入。现在每次删除一个矩形内的数字(矩形可以包括没有数字的方格)，将剩下的数字按照原来的方式从小到大填入。问最小几步操作，可以使数字只剩下$x$？$(n<=3000，x,w<=n)$.

解题思路

可以发现最终答案无论如何是不会超过$4$的。只需花两步去掉$x$这一行上面的矩形和这一行下面的矩形，现在就剩下$x$这一行的。最后在花两步去掉$x$左右两个矩形。所以最大的答案为$4$。

我们先看什么情况是一步可以达成的：

情况一：剩下数字的总数小于等于$w$,且$x$为最小或最大。

情况二：$w==1$且$x$为最小或最大。

情况三：剩下数字的总数比$w$的倍数多$1$,且$x$为最大。

情况四：$x$排在数字中第$w$位，且数字总数小于$2*w$。

我们搜索删除哪个矩形，发现影响$x$的位置发生变化的只是删除比$x$小的数字构成的矩形的大小，而与具体数字无关。

并且删除的矩形只会是$x$所处这一行上面整个矩形的子矩形，或$x$所处这一列左边或右边整个矩形的子矩形，或$x$所处这一行下面的整个矩形(因为剩下任何数字对$x$的位置变化和得到最优解没有任何益处)。

所以对于删除的矩形是$x$所处这一行上面整个矩形的子矩形时，只用枚举大小就行了。对于删除的矩形是$x$所处这一列左边或右边整个矩形的子矩形，我们保证这个子矩形一定延伸最后一行(因为我们在$x$位置确定的情况下，对于上面的情况四数字的总数越小越好，而对于其他三个情况并没有影响)，所以我们只需要枚举这个子矩形比$x$数字小所构成矩形的大小。

对于搜索我们只需要搜索两层，如果两步之后还无法一步完成，肯定答案不会比$4$优。

时间复杂度：$O(n^2)$.