自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 21:52:11，当前版本为作者最后更新于2018-08-21 09:41:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

作为一个蒟蒻我找了两个小时的规律才调出来emmmm

好像我的做法不是很一样

如果知道两个点，可以直接求出其距离

设$A(x_1,y_1),B(x_2,y_2)$且$x_1\leq x_2$

先把$B$平移到$A$所在层，这一步用了$2(x_2-x_1)$

接下来考虑平移后$B$在水平方向延伸的最大距离

可以看出这个距离是$x_2-x_1$

如果$A$和$B'$的距离不在这个范围内，我们就要给答案加上这个差

注意水平距离计算时要补成正方形来算

也就是$ans+=max(|y_1-y_2+x_2-x_1|-x_2+x_1,0)$

否则的话，还要考虑奇偶性

容易打表看出答案需要加上$y_2\ mod\ 2\ -\ y_1\ mod\ 2$

这样子就可以得到最终答案了

但是距离明明应该是对称的算出来的这个式子却不对称好气啊我也不知道为什么

代码还是挺简单的

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,s,x,y,ans=1e9+7;
int abs1(int x){return x>0?x:-x;}
int dis(int x1,int y1,int x2,int y2)
{
	if(x1>x2)swap(x1,x2),swap(y1,y2);
	int ans=(x2-x1)<<1,t=abs1(y1-y2+x2-x1)+x1-x2;
	ans+=t>0?t:(y2&1)-(y1&1);
	return k*ans;
}
int getin()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x;
}
int main()
{
	n=getin(),m=getin(),k=getin(),s=getin(),x=getin(),y=getin();
	for(int i=1;i<=m;i++)
	{
		int xx=getin(),yy=getin();
		ans=min(ans,dis(x,y,xx,yy)+1);
	}
	if(ans<=s)cout<<s-ans<<endl;
	else cout<<-1<<endl;
}

找规律是不可能的，这辈子都不可能找规律的