题目链接：开车旅行。

思路

由于小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地，因此对于每一个城市，A B 的下一个目的地是固定的。进一步地，对于每一个城市，旅行的路线固定。

看到许多大佬用的 set ，这里蒟蒻用链表处理对于每一个城市的下一个目的地：

将城市高度读进一个数组，从小到大排个序，建立链表：

            |
        |   |
        | | |
    |   | | |
    | | | | |
编号 1 2 3 4 5
高度 4 2 8 6 9

上例中，排序后高度依次为： $2$ ， $4$ ， $6$ ， $8$ ， $9$ 。编号依次为： $2$ ， $1$ ， $4$ ， $3$ ， $5$ 。

易证，对于一个城市 $c_i$ ，AB下一个的目的地一定在 $c_{i-2}$ ， $c_{i-1}$ $c_{i+1}$ ， $c_{i+2}$ 中（ $i$ 表示链表中的位置）：

   -2 -1 ci +1  +2
                |
             |  |
          |  |  |
       |  |  |  |
    |  |  |  |  |
编号 2  1  4  3  5
高度 2  4  6  8  9

处理城市时，要按排序前顺序（题面中的“自西向东”，上例中的“编号”）处理。因为按照题意，AB一直向东行驶，而不会走回头路，这样就防止处理目的地时走了回头路。处理完一个城市后，要将这个城市从链表中删除，因为这个城市他们不会再到达了。

这样，按照排序前顺序，对于每个城市，先处理目的地，再将这个城市从链表中删除，直到处理完成。

然后是进行模拟旅行。若纯暴力，一次旅行时间复杂度是 $O(n)$ 的。由于对于每一个城市，旅行的路线固定，可以用倍增加速，一次旅行时间复杂度变为 $O(\log n)$ 。

因此，解决两个问题，时间复杂度为 $O(n\log n)$ ，可以通过本题。

CODE

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	#define mset(a,b) memset(a,b,sizeof(a))
	#define ENTER printf("\n")
	const int N=100000+5,log=17,inf=2147483647-1919810;
	struct lklist{int pre,hgt,num,nxt;}list[N];
	int des[log+5][N],disA[log+5][N],disB[log+5][N];
	int n,nxtA[N],nxtB[N];
	
	void lldel(int a)
	{
		int _prev=list[a].pre;
		int _next=list[a].nxt;
		list[list[a].pre].nxt=_next;
		list[list[a].nxt].pre=_prev;
	}
	
	int choose(int a,int b,int now)
	{
  		if(!a) return list[b].num;
  		if(!b) return list[a].num;
  		if(list[now].hgt-list[a].hgt<=list[b].hgt-list[now].hgt)
  		return list[a].num;
  		else return list[b].num;
	}
	
	void init()
	{
		int ads[N];
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&list[i].hgt);
			list[i].num=i;
		}
		sort(list+1,list+1+n,[](lklist a,lklist b)->bool{return a.hgt<b.hgt;});//从小到大 
		for(int i=1;i<=n;i++)
		{
			list[i].pre=i-1;
			list[i].nxt=i+1;
			ads[list[i].num]=i;
		}list[n].nxt=0;list[1].pre=0;
		
		// For nxtAB;
        //见题解https://www.luogu.com.cn/blog/ravenclawyangrunze/solution-p1081
		for(int i=1;i<=n;i++)
		{
			int pos=ads[i],prev=list[pos].pre,next=list[pos].nxt;
			if((list[pos].hgt-list[prev].hgt<=list[next].hgt-list[pos].hgt&&prev)||next==0)
				nxtB[i]=list[prev].num,nxtA[i]=choose(list[prev].pre,next,pos);
			else
				nxtB[i]=list[next].num,nxtA[i]=choose(prev,list[next].nxt,pos);
			lldel(pos);
		}
		
		//for(int i=1;i<=n;i++) printf("%d ",nxtA[i]);ENTER;
		//for(int i=1;i<=n;i++) printf("%d ",nxtB[i]);ENTER;
		
		// For st;
		for(int i=1;i<=n;i++)
		{
        	des[0][i]=nxtB[nxtA[i]];
        	disA[0][i]=abs(list[ads[i]].hgt-list[ads[nxtA[i]]].hgt);
        	disB[0][i]=abs(list[ads[nxtA[i]]].hgt-list[ads[nxtB[nxtA[i]]]].hgt);
    	}
		for(int i=1;i<=log;i++)
			for(int j=1;j<=n;j++)
			{
				des[i][j]=des[i-1][des[i-1][j]];//AB轮流一次的目的地，而不是单独A或B
            	disA[i][j]=disA[i-1][j]+disA[i-1][des[i-1][j]];//A行程距离
            	disB[i][j]=disB[i-1][j]+disB[i-1][des[i-1][j]];//B行程距离
			}
	}
	
	void yzmain()
	{
		int x0,x0ans=0,m,s,x;
		double jud=inf;
		init();
		scanf("%d",&x0);
		for(int i=1;i<=n;i++)
		{
			int lena=0,lenb=0,gopos=i;
			for(int j=log;j>=0;j--)
			{
				if(des[j][gopos]&&(lena+lenb+disA[j][gopos]+disB[j][gopos])<=x0)
				{
					lena+=disA[j][gopos];lenb+=disB[j][gopos];
					gopos=des[j][gopos];
				}
			}
			if(nxtA[gopos]&&lena+lenb+disA[0][gopos]<=x0) lena+=disA[0][gopos];//特判。因为des[][]数组是两人一起走的 
        	if(lenb&&1.0*lena/lenb<jud)
			{
            	jud=1.0*lena/lenb;
            	x0ans=i;
        	}
    	}
    	printf("%d\n",x0ans);
    	scanf("%d",&m);
    	for(int i=1;i<=m;i++)
    	{
    		scanf("%d%d",&s,&x);
    		int lena=0,lenb=0,gopos=s;
			for(int j=log;j>=0;j--)
			{
				if(des[j][gopos]&&(lena+lenb+disA[j][gopos]+disB[j][gopos])<=x)
				{
					lena+=disA[j][gopos];lenb+=disB[j][gopos];
					gopos=des[j][gopos];
				}
			}
			if(nxtA[gopos]&&lena+lenb+disA[0][gopos]<=x) lena+=disA[0][gopos]; 
        	printf("%d %d\n",lena,lenb);
		}
		return;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	_yz::yzmain();
	return 0;
}