自动搬运

查看原文

来自洛谷，原作者为

	LHF qwq

搬运于2025-08-24 22:31:02，当前版本为作者最后更新于2022-10-25 20:13:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到题解区都是双 $\log$ 的做法，我提供一种单 $\log$ 的做法。

为了方便，我们先曼哈顿距离转切比雪夫距离。

看到了第 $k$ 大，我们考虑二分答案，考虑如何判断是否合法。

这里我们采取对平面进行分块，假设当前二分的答案为 $d$，我们就每 $d$ 个分成一块。

如何统计答案呢？考虑到直接对于当前点所在的块以及相关的八个方向爆枚一通。

可以证明，这样的复杂度是 $O(n)$ 的。

所以总复杂度 $O(n\log a)$。

不过常数太大了，所以跑得跟两个 $\log$ 估计也差不多。

#include<cstdio>
#include<algorithm>
#include<unordered_map>
#include<vector>
#define ll long long
#define pir pair<ll,ll>
using namespace std;
const int N=5e5+10,P=1e7+7;
vector<pir> v[N];
namespace ht
{
	struct edge{
		int next;
		ll x,y;
	}e[N];
	int first[P],len,q[N],cnt;
	int qry(ll x,ll y,bool p)
	{
		int w=(x*1919+y*811)%P;
		if(w<0) w+=P;
		for(int i=first[w];i;i=e[i].next)
			if(e[i].x==x&&e[i].y==y) return i;
		if(!p) return -1;
		e[++len]=edge{first[w],x,y};
		if(!first[w]) q[++cnt]=w;
		first[w]=len;
		return len;
	}
	void clear()
	{
		for(int i=1;i<=len;i++) v[i].clear();
		for(int i=1;i<=cnt;i++) first[q[i]]=0;
		len=cnt=0;
	}
}
int len,k,p,n;
ll ans[N<<2];
ll calc(ll a,ll b)
{
	if(a>=0) return a/b;
	else return (a+1)/b-1;
}
void push(ll x)
{
	ans[++len]=x;
}
void work(ll d,ll x,ll y,int i)
{
	if(i<0) return;
	if(len>=k&&p) return;
	ll w;
	for(pir a:v[i])
	{
		w=max(abs(a.first-x),abs(a.second-y));
		if(w<=d) push(w);
	}
}
const int f1[10]={0,1,1,1,0,-1,-1,-1,0},f2[10]={0,1,0,-1,-1,-1,0,1,1};
ll x[N],y[N],a,b;
bool chk(ll d)
{
	ht::clear(),len=0;
	for(int i=1;i<=n;i++)
	{
		a=calc(x[i],d),b=calc(y[i],d);
		for(int k=0;k<9;k++)
			work(d,x[i],y[i],ht::qry(a+f1[k],b+f2[k],0));
		v[ht::qry(a,b,1)].push_back({x[i],y[i]});
		if(p&&len>=k) return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&a,&b),x[i]=a+b,y[i]=a-b;
	ll l=1,r=4e9,mid;
	p=1;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(chk(mid)) r=mid;
		else l=mid+1;
	}
	chk(l);
	sort(ans+1,ans+len+1);
	for(int i=1;i<=k;i++)
		printf("%lld\n",ans[i]);
}