这道题：你不仅要学会两人交换开车，还要做到高效驾驶。
·分析：
在拨开花哨题目的迷雾之后，发现两个重要突破口：
①从每个点开始，他们的路径是一定的，不存在决策选取。
②要是n,m没有那么大的话，就直接预处理每个点对于每个人开车至下一个点的位置和路程(n2)，然后两个问题都可以从起点（第一问就是枚举起点）开始预处理的数据来“轮流开车”。（这一个突破口有点过于顶尖了，因为这是过70%数据的题解）
下图是这种做法的简图。
用des[i][0],des[i][1]分别表示在城市i小B开车和小A开车前往的下一个目的地。用Min[i][0],Min[i][1]分别与上面的数组对应，表示对应路径的长度（注意是反向枚举）
·无论是第一问还是第二问，都可以从起点s开始，通过des,Min数组来向后开车并记录两人各自走的路程。
·很美妙但又很遗憾，仅仅这样做时间复杂度：(n2+nm)
·这道题真正的考点就出来了：考察我们的优化技能。
·很轻易可以发现，这道题的数据范围又给了我们很大的提示：
n<=100000。这启示我们：nlogn
·余下的事情就是把时间复杂度中的部分n替换成logn,使得时间复杂度保持在：O(mlogn+nlogn)【这有点过于顶尖了】
·在本题中大米饼的对策是：预处理des,Min(这原来是一个n2)时使用STL中的set来维护(降为nlogn),在路径上使用倍增法，
·最后一个值得注意的一点，倍增的每一段为了方便操作，这里AB各走一次算成一段，不过倍增的距离还是对AB进项单独维护。整个程序还有许多细节需要注意。 wow!
#include<stdio.h>
#include<algorithm>
#include<set>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define ro(i,a,b) for(int i=a;i>=b;i--)
#define inf 2147483645
#define eps 0.000003
using namespace std;const int N=;
int n,m,s,h[N],des[N][],Min[N][],To[N][],dis[N][][],tot[],x;
struct info{int h,id;bool operator<(const info a)const{return h<a.h;};};
set<info>box;set<info>::iterator I;int A(int t){return t<?-t:t;}
void consider(int i,info p)
{
int j=p.id;
if((A(h[i]-h[j])<Min[i][])||(Min[i][]==A(h[i]-h[j])&&h[j]<h[des[i][]]))
{
if((Min[i][]<Min[i][])||(Min[i][]==Min[i][]&&h[des[i][]]<h[des[i][]]))
Min[i][]=Min[i][],des[i][]=des[i][];
Min[i][]=A(h[i]-h[j]),des[i][]=j;
}
else if((A(h[i]-h[j])<Min[i][])||(Min[i][]==A(h[i]-h[j])&&h[j]<h[des[i][]]))
Min[i][]=A(h[i]-h[j]),des[i][]=j;
}
void doubling(int i,int val)
{
ro(k,,)if(dis[i][k][]+dis[i][k][]<=val&&To[i][k])
val-=(dis[i][k][]+dis[i][k][]),
tot[]+=dis[i][k][],tot[]+=dis[i][k][],i=To[i][k];
if(des[i][]&&Min[i][]<=val)tot[]+=Min[i][];
}
int main(){scanf("%d",&n);go(i,,n)scanf("%d",&h[i]),Min[i][]=Min[i][]=inf;
ro(i,n,)
{
box.insert((info){h[i],i});
I=box.find((info){h[i],i});++I;
if(I!=box.end())consider(i,*I),++I,I!=box.end()?consider(i,*I),:,--I;--I;
if(I!=box.begin())--I,consider(i,*I),I!=box.begin()?--I,consider(i,*I),:;
} go(i,,n)To[i][]=des[des[i][]][],
dis[i][][]=Min[i][],dis[i][][]=Min[des[i][]][]; go(k,,)go(i,,n)To[i][k]=To[To[i][k-]][k-],
dis[i][k][]=dis[i][k-][]+dis[To[i][k-]][k-][],
dis[i][k][]=dis[i][k-][]+dis[To[i][k-]][k-][]; scanf("%d",&x);double rate=inf;int pos=;h[]=-inf;go(i,,n)
{
tot[]=tot[]=;doubling(i,x);double tmp=tot[]?1.0*tot[]/tot[]:inf;
if(tmp-rate<eps&&tmp-rate>-eps&&h[i]>h[pos])pos=i;
if(rate-tmp>eps)pos=i,rate=tmp;
} printf("%d\n",pos);scanf("%d",&m);go(i,,m)
{
scanf("%d%d",&s,&x);
tot[]=tot[]=;doubling(s,x);
printf("%d %d\n",tot[],tot[]);
}
return ;
}//Paul_Guderian
只许集中，不许分散。————海因茨·威廉·古德里安