登录
二分 & 贪心 & 单调指针
解法：二分 & 贪心 & 单调指针
最小值最大，首先尝试二分答案 $l$。注意数据范围 $k \ge 4$，因此答案至多为正方形的边长。
只考虑小等于边长的答案有什么好处呢？考虑选了一个点 $P$ 之后，会导致哪些点不可选。因为所有点都在边界上，所以我们想象从这个点出发，往两边走出去，会发现只要不走到对面那条边上，我们越往两边走，距离 $P$ 就越远。我们从原点开始，把所有点按逆时针顺序编个号，那么如果不考虑对边，选择 $P$ 只会影响包含 $P$ 的一个区间。而由于对边到 $P$ 的距离至少有一个边长，因此我们确实可以不考虑对边。
现在问题变为：在环上有 $n$ 个点，选择至少 $k$ 个点，使得相邻两点的距离至少为 $l$。这个问题在链上是很好做的，我们先选第一个点，然后每次选择最左边的可选点即可。因为每个点的影响距离是固定的，所以选择最左边的点可以给右边留下更多可选的点。
可是环上的问题怎么办呢？我们发现，环上最大的问题在于：所选的最后一个点到第一个点的距离可能不足 $l$，那我们就不知道第一个点该选哪个比较好。
不知道选哪个的时候，那就枚举吧！可是枚举第一个点选哪个，再跑一边贪心，复杂度会变成 $\mathcal{O}(n^2)$。如何才能降低复杂度呢？
这时候就可以尝试单调性了。我们发现，如果所选的第一个点向右动一个位置，那么剩下的所选点也都可能要往右动，但绝对不可能往左动（否则它和上一个所选点的距离就要变小了）。这正是我们想要的单调性。
因此我们先假设选择第一个点，然后按链上的贪心选出 $k$ 个点。如果此时 $k$ 个点都选不出来，说明链上的问题无解，而环上的问题比链上的还多一个限制，那就更误解了，直接返回 false。
如果链上的问题有解，但所选的最后一个点到第一个点的距离不足 $l$，我们就得按逆时针顺序枚举第一个点。每一个点的右移可能会波及到下一个点，因此我们还要右移每个所选点，直到它到上一个所选点的距离至少为 $l$。调整完成后，再检查最后一个点到第一个点的距离。
细心的读者可能还有一个疑问：单调指针的复杂度等于每个指针最多移动的步数，那么每个指针最多移动几步呢？如果最后一个点调整之后，甚至反超了第一个点，那肯定就无解了。而第一个点的下标范围只有 $0$ 到 $(n - 1)$，说明最后一个点的下标不会超过 $2n$。因此每个指针最多移动 $2n$ 步。
因此整体复杂度 $\mathcal{O}(nk\log X)$，其中 $X = 10^9$ 是边长的值域。
参考代码（c++）
class Solution {
public:
int maxDistance(int side, vector<vector<int>>& points, int K) {
int n = points.size();
// 按逆时针顺序给点排序
auto ord = [&](long long x, long long y) {
long long s = side;
if (y == 0) return x;
else if (x == s) return s + y;
else if (y == s) return s * 3 - x;
else return s * 4 - y;
};
sort(points.begin(), points.end(), [&](vector<int> &a, vector<int> &b) {
return ord(a[0], a[1]) < ord(b[0], b[1]);
});
// 求第 i 个点到第 j 个点的距离
auto dis = [&](int i, int j) {
return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
};
// 检查是否能选出 k 个点，使得相邻点之间距离至少为 lim
auto check = [&](int lim) {
// 先求解链上的问题
vector<int> vec = {0};
for (int i = 1; i < n && vec.size() < K; i++)
if (dis(i, vec.back()) >= lim) vec.push_back(i);
// 链上问题无解，环上更无解了
if (vec.size() < K) return false;
// 选的第一个点刚好就是对的
if (dis(vec[0], vec.back()) >= lim) return true;
// 枚举第一个点选哪个
for (int i = 1; i < n && vec.back() < n * 2; i++) {
vec[0] = i;
// 调整每个点，使得距离符合要求
for (int j = 1; j < K; j++) {
while (dis(vec[j] % n, vec[j - 1] % n) < lim) {
vec[j]++;
// 每个指针最多移动 2n 步
if (vec[j] >= n * 2) return false;
}
}
// 检查最后一个点到第一个点的距离
if (vec.back() < i + n && dis(i, vec.back() % n) >= lim) return true;
}
return false;
};
// 二分答案
int head = 1, tail = side;
while (head < tail) {
int mid = (head + tail + 1) >> 1;
if (check(mid)) head = mid;
else tail = mid - 1;
}
return head;
}
};
