Codeforces Round #477 

C. Stairs and Elevators

题目链接

题意：给你一栋高n层，每一层由m个部分组成，可以看成是一个矩阵划分成行和列。给你一cl,ce分别表示有个楼梯和电梯，然后给你一个v表示电梯的速度。接下来行表示每个电梯在对应楼 层的位置，在

接下来行表示对应电梯口的位置。然后有q个询问，每个询问包括一个起点和终点，问你从起点到终点的最短时间。

思路：这道题的坑点挺多的.....首先是特判起点和终点是否在同一层，如果在同一层直接走过去即可，不是同一层

的话，需要从起点开始，寻找最近的楼梯和电梯，分别计算用楼梯和电梯到达终点的，取最小值即可。注意边界的问题，还有就是用lower_bound()找出大于等于起点的楼梯电梯位置时，需要如果存在大于或小于这个位置的楼梯和电梯时，也要加入计算。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int numa[maxn],numb[maxn];
int main() {int n,m,a,b,v;cin>>n>>m>>a>>b>>v;for(int i=0; i<a; i++)scanf("%d",&numa[i]);for(int i=0; i<b; i++)scanf("%d",&numb[i]);sort(numa,numa+a);sort(numb,numb+b);int q,x1,y1,x2,y2;cin>>q;for(int i=1; i<=q; i++) {scanf("%d %d %d %d",&y1,&x1,&y2,&x2);if(y1==y2){printf("%d\n",abs(x2-x1));continue;}int posa=lower_bound(numa,numa+a,x1)-numa;        //找出刚好大于等于x1位置的楼梯的下标 int posb=lower_bound(numb,numb+b,x1)-numb;        //找出刚好大于等于x1位置的电梯的下标  if(posa==a)  //如果不存在，则最近的位置为最后那个楼梯的位置，若posa=-1，则表示不存在楼梯 posa=a-1;if(posb==b)//如果不存在，则最近的位置为最后那个电梯的位置，若posa=-1，则表示不存在楼梯 posb=b-1;int Mina=INF;int Minb=INF;if(posa!=-1) {int mina=abs(numa[posa]-x1);Mina=mina+abs(y2-y1)+abs(x2-numa[posa]);  //计算使用posa位置的楼梯 if(posa-1>=0){        //计算使用posa-1位置的楼梯 Mina=min(Mina,abs(x1-numa[posa-1])+abs(y2-y1)+abs(x2-numa[posa-1]));}if(posa+1<a){        //计算使用posa+1位置的楼梯 Mina=min(Mina,abs(x1-numa[posa+1])+abs(y2-y1)+abs(x2-numa[posa+1]));}}if(posb!=-1) {int minb=abs(numb[posb]-x1);  //计算使用posb位置的电梯 Minb=minb+abs(y2-y1)/v+abs(x2-numb[posb]);if(posb-1>=0){        //计算使用posb-1位置的电梯Minb=min(Minb,abs(x1-numb[posb-1])+abs(y2-y1)/v+abs(x2-numb[posb-1]));}if(posb+1<b){         //计算使用posb-1位置的电梯Minb=min(Minb,abs(x1-numb[posb+1])+abs(y2-y1)/v+abs(x2-numb[posb+1]));}if(abs(y2-y1)%v!=0)   Minb++;}int Min=min(Mina,Minb);printf("%d\n",Min);}return 0;
}