自动搬运

查看原文

来自洛谷，原作者为

	UMS2 这个家伙很懒，什么也没有留下(

搬运于2025-08-24 22:23:20，当前版本为作者最后更新于2024-08-09 07:51:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目描述

一个大小为 $R \times C$ 的棋盘上有 $n$ 个棋子，每次询问 $(x,y)$ 的返回值为 $\sum(|x_i-x|+|y_i-y|)$。至多询问 $k$ 次，求最小的返回值。

$n\le 100;R,C\le1\times 10^7;k_{min}=75$。

思路

60pts

注意到在 $x$ 轴上移动并不会改变 $y$ 轴上的总距离，反之亦然。而绝对值函数的和是一个不严格的单谷函数。故尝试在 $x$ 轴和 $y$ 轴上分别三分。

这样的询问最大次数为 $4\log_{\frac{3}{2}}10^7 \approx 160$ 。而前 40pts 只有一半的询问次数，共 60pts。

int l=1,r=m;
while(l<r){
	int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
	if(ask(1,lmid)<ask(1,rmid))r=rmid-1;
	else l=lmid+1;
}
resy=l;

l=1,r=n;
while(l<r){
	int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
	if(ask(lmid,resy)<ask(rmid,resy))r=rmid-1;
	else l=lmid+1;
}
resx=l;
ans=ask(resx,resy);
cout<<"! "<<ans;

80pts

注意到我们没有必要使用三分，由于本题函数是离散的，我们可以使用二分，这样的询问最大次数为 $4\log_210^7\approx 94$。

int l=1,r=m;
while(l<r){
	int mid=l+r>>1;
	int lmid=mid,rmid=min(mid+1,m);
	if(ask(1,lmid)<ask(1,rmid))r=rmid-1;
	else l=lmid+1;
}
resy=l;

l=1,r=n;
while(l<r){
	int mid=l+r>>1;
	int lmid=mid,rmid=min(mid+1,n);
	if(ask(lmid,resy)<ask(rmid,resy))r=rmid-1;
	else l=lmid+1;
}
resx=l;

ans=ask(resx,resy);
cout<<"! "<<ans;

100pts

注意到我们二分时并不需要关心另一个轴上的位置，于是可以一起二分，共用一个点。这样可以做到 $3\log_210^7 \approx 70$ 次询问，足以通过本题。

int l=1,r=m,nl=1,nr=n;
while(l<r||nl<nr){
	int amid=l<r?l+r>>1:1,bmid=nl<nr?nl+nr>>1:1;
	int nans=ask(bmid,amid);
	if(l<r){
		if(nans<ask(bmid,amid+1))r=amid;
		else l=amid+1;
	}
	if(nl<nr){
		if(nans<ask(bmid+1,amid))nr=bmid;
		else nl=bmid+1;
	}
}
resx=nl,resy=l;
ans=ask(resx,resy);
cout<<"! "<<ans;