Hello everybody
今天我为大家分享下跳跃距离 <20087>的题解
通过观察我们可以得知，当x1=x2时
最小行走步数为
abs(y1-y2)
在普通代码中
我们应使用dfs枚举所有情况
使用
方向数组
dx[]={1,1,-1,-1},dy[]={1,-1,1,-1};
从 (x1,x2)走到(x1+k*dx[i],y1+k*dy[i])
比较 x1+k*dx[i]=x2 时和 y1+k*dy[i]=y2 到达目标点时的最小步数
这里以 x1+k*dx[i]=x2 举例
通过移项得
k=(x2-x1)/dx[i]
此时
y1=(x2-x1)/dx[i]*dy[i]
行走步数为
abs((x2-x1)/dx[i]*dy[i]-y2)+abs(x2-x1)
通过比较这8种情况，我们可以找到 从(x1,y1) 到(x2,y2)的最小步数
在主函数中，判断A是否能到达B点
通过打表可知 A只能到达与其 x,y %2余数相同的点
<如下图>
X * X * X
* A * X *
X * X * X
即判断
abs(x1-x2)mod2 ?= abs(y1-y2)mod2
依题意
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
}
}
我们会发现
Time limit
如果你的代码写的没问题的话你最多只能得到20分
该代码时间复杂度为 O(n^2) TLE 是必然的
SO
如何改AC代码呢？
如果你知识够渊博的话 你应该听过曼哈顿距离和切比雪夫距离
(x1,y1)和(x2,y2)之间的哈顿距离和切比雪夫距离分别为
abs(x1-x2)+abs(y1-y2)
max(abs(x1-x2),abs(y1-y2))
我们可以将切比雪夫距离的坐标 (x,y) 转化为曼哈顿距离 (x+y,x-y)
通过简单的带入可得所得的曼哈顿距离为原切比雪夫距离的2倍
所以最后的结果别忘了/2
当点数从2个变为n个时
第一个点与其余点曼哈顿距离之和为
\sum_{i=2}^nabs(x[1]-x[i])
当x1到xn降序排列时 原式可化为
(n-1)*x1-\sum_{i=2}^nx[i]
将x[1]变为x[i]也是同理
原式=
(n-i)*x[i]-\sum_{j=i+1}^nx[j]
所以原代码得到了化简
其等式后的
\sum_{j=i+1}^nx[j]
我们可以用后缀和解决
具体代码如下
for(int i=n;i>=1;i--){
sum[i]=sum[i+1]+x[i];
}
在使用后缀和时
for(int i=1;i<=n-1;i++){
ans+=sum[i+1]-(n-i)*x[i];
}
最后的能否到达的奇偶性判断就交给你们自己了