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\) 条路所需要的钱。

解析

首先你要知道什么是曼哈顿距离和切比雪夫距离及相互转化。

推荐学习曼哈顿距离与切比雪夫距离的互化。

现在我把点坐标转化后就是要求解这样一个问题：

选出前 \(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;

}