本文主要是介绍开车旅行（NOIP2012提高组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
这道题最基本的思路是用倍增，但是其实它的难点在预处理部分。
倍增的部分此次就不细说了，和之前的最近公共祖先的思想类似。
我们主要来探讨一下预处理的部分。
我们需要预处理出每个城市小A和小B的选择目标和对应的距离，接下来就可以处理出进行2k轮开车的目的地和距离了。所以前者才是重中之重，而前者如果要用暴力的方法会tle的。
有人可能会疑惑，我们找当前点的后面两三个不就可以了？为什么会tle呢？
实际上并不是序号相差很远距离就很远，实际上有可能第一个城市和最后一个城市最近，可以举个例子，城市海拔如下：
1 3 4 5 6 7 8 9 10 11 2
也许你也会有疑问，不是说右边的城市在左边城市的东边吗？这可能吗？
注意这题并不是线性的，而是2D的。所以可以画出如下的图：
所以，这么看来，暴力算法的复杂度就是n方，就会超时。
所以我们需要换种方法。
我们不妨换种顺序，因为是用海拔来决定高度，所以海拔相距最近的，一定是距离最近的。
所以我们可以按照海拔进行排序，排好序后就按照这个顺序建立双向链表。
这时我们就知道了，对于某一城市，小a和小b要么没有选择，要么选择的城市一定在当前城市链表中的前两个和两个中。
为什么不是前一个和后一个？因为如果一个点在链表边上，它就只有一侧，所以把特殊情况考虑在内，就是前两个和后两个。
那么你可能又会觉得奇怪，万一这几个当中有城市在当前城市的西边怎么办？这样这个范围就可能不够了？
所以我们的处理顺序就成了很大的很关键，我们按照城市编号顺序去处理每个城市的目标，处理完后就把当前城市删除（这也是用双向链表的原因），这样每次处理就可以保证当前链表中的其他城市均在当前城市的东边，而保证我们所取的范围是够的。
当然你也许还会有疑问，那我怎么定位要处理的城市在链表中的位置呢？
这个准备的指针数组就好了。
这样就可以把预处理的复杂度从O(n2)降低到O(n)，这样就可以过了
下面是参考代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAX 2000000000
using namespace std;
const int maxn=100005;
struct City{int num;int h;City *last,*next;
}city[maxn];
City *pos[maxn];
long long n,m,x0,ss[maxn],xx[maxn],h[maxn],maxk;
long long aaim[maxn],baim[maxn],adis[maxn],bdis[maxn];
long long longdis[maxn][20],longaim[maxn][20];
long long alongdis[maxn][20],alongaim[maxn][20];
long long s0,da=-1,db=-1;
void fun1(long long curs){long long tot=0,cura=0,curb=0,curn=curs;for(int k=maxk;k>=0;k--){if(longaim[curn][k]!=0&&longdis[curn][k]+tot>x0){continue;}if(longaim[curn][k]==0){continue;}tot+=longdis[curn][k];cura+=alongdis[curn][k];curn=longaim[curn][k];}curb=tot-cura;if(aaim[curn]!=0&&tot+adis[curn]<=x0){tot+=adis[curn];cura+=adis[curn];}if(da==-1){s0=curs;da=cura;db=curb;}else if(db==0&&curb==0&&h[curs]>h[s0]){s0=curs;da=cura;db=curb;}else if(db==0){s0=curs;da=cura;db=curb;}else if(curb==0){}else if(da*curb>db*cura){s0=curs;da=cura;db=curb;}else if(da*curb==db*cura&&h[curs]>h[s0]){s0=curs;da=cura;db=curb;}
}
void fun2(long long s,long long xi){long long tot=0,cura=0,curb=0,curn=s;for(int k=maxk;k>=0;k--){if(longaim[curn][k]!=0&&longdis[curn][k]+tot>xi){continue;}if(longaim[curn][k]==0){continue;}tot+=longdis[curn][k];cura+=alongdis[curn][k];curn=longaim[curn][k];}curb=tot-cura;if(aaim[curn]!=0&&tot+adis[curn]<=xi){tot+=adis[curn];cura+=adis[curn];}printf("%d %d\n",cura,curb);
}
int cmp(City a,City b){return a.h<b.h;
}
void update(City cur,City aim){if((abs(cur.h-aim.h)<bdis[cur.num])||(abs(cur.h-aim.h)==bdis[cur.num]&&aim.h<pos[baim[cur.num]]->h)){adis[cur.num]=bdis[cur.num];aaim[cur.num]=baim[cur.num];bdis[cur.num]=abs(cur.h-aim.h);baim[cur.num]=aim.num;}else if((abs(cur.h-aim.h)<adis[cur.num])||(abs(cur.h-aim.h)==adis[cur.num]&&aim.h<pos[aaim[cur.num]]->h)){adis[cur.num]=abs(cur.h-aim.h);aaim[cur.num]=aim.num;}
}
int main(){scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%lld",&city[i].h);adis[i]=bdis[i]=MAX;city[i].num=i;}scanf("%lld%lld",&x0,&m);for(int i=0;i<m;i++){scanf("%lld%lld",&ss[i],&xx[i]);}sort(city+1,city+n+1,cmp);for(int i=1;i<=n;i++){if(i==1){city[i].last=NULL;}else{city[i].last=&city[i-1];}if(i==n){city[i].next=NULL;}else{city[i].next=&city[i+1];}pos[city[i].num]=&city[i];}for(int i=1;i<=n;i++){City *p;p=pos[i]->last;if(p!=NULL){update(*pos[i],*p);p=p->last;if(p!=NULL){update(*pos[i],*p);}}p=pos[i]->next;if(p!=NULL){update(*pos[i],*p);p=p->next;if(p!=NULL){update(*pos[i],*p);}}if(pos[i]->next!=NULL){pos[i]->next->last=pos[i]->last;}if(pos[i]->last!=NULL){pos[i]->last->next=pos[i]->next;}} for(int i=1;i<=n;i++){if(aaim[i]!=0&&baim[aaim[i]]!=0){longdis[i][0]=adis[i]+bdis[aaim[i]];longaim[i][0]=baim[aaim[i]];alongdis[i][0]=adis[i];alongaim[i][0]=baim[aaim[i]];}else{longaim[i][0]=0;longdis[i][0]=MAX;alongdis[i][0]=MAX;alongaim[i][0]=0;}}for(int k=1;(1<<k)<=n;k++){for(int i=1;i<=n;i++){if(longaim[i][k-1]!=0&&longaim[longaim[i][k-1]][k-1]!=0){longdis[i][k]=longdis[i][k-1]+longdis[longaim[i][k-1]][k-1];longaim[i][k]=longaim[longaim[i][k-1]][k-1];}else{longdis[i][k]=MAX;longaim[i][k]=0;}if(alongaim[i][k-1]!=0&&alongaim[alongaim[i][k-1]][k-1]!=0){alongdis[i][k]=alongdis[i][k-1]+alongdis[alongaim[i][k-1]][k-1];alongaim[i][k]=alongaim[alongaim[i][k-1]][k-1];}else{alongdis[i][k]=MAX;alongaim[i][k]=0;}}maxk=k;} for(int i=1;i<=n;i++){fun1(i);}printf("%d\n",s0);for(int i=0;i<m;i++){fun2(ss[i],xx[i]);}return 0;
}
这篇关于开车旅行（NOIP2012提高组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
