P7561[JOISC 2021 Day2] 道路の建設案 (Road Construction) 题解
题目描述
JOI 国是一个 \(x\times y\) 的二维平面，王国里有 \(n\) 个城镇，分别编号为 \(1, 2, \cdots, n \in [1,2.5 \times 10^5]\)，其中第 \(i\) 个城镇的 坐标 为 \((x_i, y_i)\)。
在 JOI 国，正计划修建连接两座城镇的路（下文简称：「修路的项目」），路有 \(k\) 条。连接两个不同的城镇 \(a\) 和 \(b\) 将花费 \(|x_a − x_b| + |y_a − y_b|\) 元。若有一条连接 \(c\)，\(d\) 的路，则不需要也不可以在建一条连接 \(d\)，\(c\) 的路，因为它们是相同的。
你要管理这个「修路的项目」，为了计算花费情况，你得弄明白连接一些城镇所需的花费。在这 \(\dfrac{n\cdot(n-1)}{2}\) 条道路中，你想了解最便宜的 \(k\) 条道路的花费。
给你城镇的坐标以及 \(k\)，请计算最便宜的 \(k\) 条路所需要的钱。
解析
首先你要知道什么是曼哈顿距离和切比雪夫距离及相互转化。
推荐学习曼哈顿距离与切比雪夫距离的互化。
现在我把点坐标转化后就是要求解这样一个问题：
\[\max(|x_i-x_j|,|y_i-y_j|) \]选出前 \(k\) 小。
我们可以二分一下第 \(k\) 小的值 \(mid\)，再 check 有没有 \(k\) 个距离小于 mid 。
同时我们不需要真正数有多少点对，点对数 \(≥k\) 时直接返回 true 即可。
具体操作是先按照 \(x\) 排序。
假设当前到了 \(x_i\) ，将所有 \([x_i-mid,x_i]\) 的点放入 set 里面，
之前在 \([x_{i-1}-mid,x_{i-1}]\) 里面的但不在 \([x_i-mid,x_i]\) 删掉（用双指针维护）。
然后在 set 里面先二分找到 \(y_i-mid\)，枚举到 \(y_i + mid\) ，每枚举到一个就 ++ans。
当 ans >= k 的时候就直接 return 。
最后如何求出答案？
找到第 \(k\) 小的值 \(mid\) 了之后，再 check 一次 \(mid-1\)，这样一定可以找到小于 \(k\) 个长度小于 \(mid\) 的长度，最后再用 \(mid\) 把 \(k\) 补满，就是答案。
因为 \(ans >= k\) 会 return 所以严格 \(O(n\log n)\)。
温馨提示
1.因为转化为切比雪夫距离，又要互相加减，所以要开 long long 。
2.用 multiset ，因为可能有相同长度。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e7 + 10;
int n, k;
ll x,y,an[N],ans = 0,l,r,mid;
queue<int>q;
struct node{
ll x, y;
bool operator <(const node a)const{
return x < a.x;
}
}p[N];
struct Node{
ll x, y;
bool operator <(const Node a)const{
return y < a.y;
}
};
multiset<Node>s;
void input(){
cin>>n>>k;
for(int i = 1; i <= n; ++i){
cin>>x>>y;
p[i].x = x - y;
p[i].y = x + y;
}
sort(p + 1,p + 1 + n);
}
bool check(ll mid){
q = queue<int>();
s = multiset<Node>();
ans = 0;
for(int i = 1; i <= n; ++i){
while(q.size() && p[i].x - p[q.front()].x > mid){
multiset<Node>:: iterator w = s.find((Node){0,p[q.front()].y});
s.erase(w);
q.pop();
}
multiset<Node>::iterator lz = s.lower_bound((Node){0,p[i].y - mid});
while(lz != s.end() && (*lz).y <= p[i].y + mid){
an[++ans] = max(abs((*lz).x - p[i].x),abs((*lz).y - p[i].y));
if(ans >= k) return 1;
++lz;
}
q.push(i);
s.insert((Node){p[i].x,p[i].y});
}
return 0;
}
void op(){
l = 0,r = 4e9,mid;
while(l < r){
mid = (l + r) >> 1;
if(check(mid)){
r = mid;
}else{
l = mid + 1;
}
}
check(l - 1);
}
void output(){
sort(an + 1,an + 1 + ans);
int i;
for(i = 1; i <= ans; ++i){
cout<<an[i]<<'\n';
}
for(; i <= k; ++i){
cout<<l<<'\n';
}
}
int main(){
cin.tie(0)->sync_with_stdio(false);
input();
op();
output();
return 0;
}