教主的花园

Description

【问题背景】
　　LHX教主最近总困扰于前来膜拜他的人太多了，所以他给他的花园加上了一道屏障。

【问题描述】
　　可以把教主的花园附近区域抽像成一个正方形网格组成的网络，每个网格都对应了一个坐标（均为整数，有可能为负），若两个网格(x1, y1)，(x2, y2)有|x1 – x2| + |y1 – y2| = 1，则说这两个网格是相邻的，否则不是相邻的。
　　教主在y = 0处整条直线上的网格设置了一道屏障，即所有坐标为(x, 0)的网格。当然，他还要解决他自己与内部人员的进出问题，这样教主设置了N个入口a1, a2, …, aN可供进出，即对于y = 0上的所有网格，只有 (a1, 0)，(a2, 0)， ……， (aN, 0) 可以通过，之外的所有纵坐标为0的网格均不能通过，而对于(x, y)有y不为0的网格可以认为是随意通过的。
　　现在教主想知道，给定M个点对(x1, y1)，(x2, y2)，并且这些点均不在屏障上，询问从一个点走到另一个点最短距离是多少，每次只能从一个格子走到相邻的格子。

Input
　　输入的第1行为一个正整数N，为屏障上入口的个数。
　　第2行有N个整数，a1, a2, …, aN，之间用空格隔开，为这N个入口的横坐标。
　　第3行为一个正整数M，表示了M个询问。
　　接下来M行，每行4个整数x1, y1, x2, y2，有y1与y2均不等于0，表示了一个询问从(x1, y1)到(x2, y2)的最短路。

Output
　　输出共包含m行，第i行对于第i个询问输出从(x1, y1)到(x2, y2)的最短路距离是多少。

Sample Input
2
2 -1
2
0 1 0 -1
1 1 2 2

Sample Output
4
2

Data Constraint

Hint

【数据规模】
　　对于20%的数据，有n，m≤10，ai，xi，yi绝对值不超过100；
　　对于40%的数据，有n，m≤100，ai，xi，yi绝对值不超过1000；
　　对于60%的数据，有n，m≤1000，ai，xi，yi绝对值不超过100000；
　　对于100%的数据，有n，m≤100000，ai，xi，yi绝对值不超过100000000。
.
.
.
.
.
.
.
.

分析

题目大意就是在一个平面直角坐标系中x轴上是一道屏障，但上面有n个开头，要求两个点的距离
显然，这题可以分类讨论来做
①两个点的y坐标同号，直接求曼哈顿距离输出
如果不行，则二分一个在中间的开口
②如果这个开口位于两个点中间，求出两个点分别到开口的曼哈顿距离相加并输出
③否则判断一下它距离哪一个端点近，就由哪里绕过去
虽然此时的pos值不一定准确，但十分接近，真实值一定出现在pos-1，pos，pos+1中，求最小值输出就好了
.
.
.
.
.
.
.

程序：

uses math; var x1,y1,x2,y2,i,n,m,pos:longint; a:array[-1..100002]of longint; t1,t2,t3:int64;procedure swap(x,y:longint); var xc:longint; beginxc:=x1;x1:=x2;x2:=xc; end;function find(x:longint):longint; var l,r,mid,k:longint; beginl:=1;r:=n;k:=n;while l<=r dobeginmid:=(l+r) div 2;if a[mid]<x then l:=mid+1 elsebeginr:=mid-1;k:=mid;end;end;exit(k); end;procedure kp(l,r:longint); var i,j,mid:longint; beginif l>=r then exit;i:=l;j:=r;mid:=a[(i+j) div 2];repeatwhile a[i]<mid do inc(i);while a[j]>mid do dec(j);if i<=j thenbegina[-1]:=a[i];a[i]:=a[j];a[j]:=a[-1];inc(i);dec(j);end;until i>j;kp(l,j);kp(i,r); end;beginreadln(n);for i:=1 to n doread(a[i]);kp(1,n);readln;readln(m);for i:=1 to m dobeginreadln(x1,y1,x2,y2);if (y1<0)and(y2<0)or(y1>0)and(y2>0) thenbeginwriteln(abs(x1-x2)+abs(y1-y2));continue;end;if x1>x2 then swap(x1,x2);pos:=find((x1+x2) div 2);if (a[pos]>=x1)and(x2>=a[pos]) then writeln(abs(x1-x2)+abs(y1-y2)) elsebegint1:=abs(a[pos]-x1)+abs(a[pos]-x2)+abs(y1-y2);t2:=200000000;t3:=200000000;if pos>1 then t2:=abs(a[pos-1]-x1)+abs(a[pos-1]-x2)+abs(y1-y2);if pos<n then t3:=abs(a[pos+1]-x1)+abs(a[pos+1]-x2)+abs(y1-y2);t1:=min(t1,t2);t1:=min(t1,t3);writeln(t1);end;end; end.

转载于:https://www.cnblogs.com/YYC-0304/p/9499978.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的教主的花园的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。