双向链表预处理+倍增优化+暴力求解

首先这道题，可以发现一个很明显的性质，由于不可以往回开，所以对于每一个城市，它的第一近城市和它的次近城市肯定是唯一的，这样就可以用双向链表预处理出每个点的fh[]和sh[],不会的可以参考这里 https://www.acwing.com/problem/content/138/ ;

因为每个点每天可以走到的下一点也是一定的，所以又可以预处理，不过有优化，暴力的话应该会有O(n^2)的时间复杂度，数据范围是1e5,会TLE，所以考虑倍增，为什么可以倍增呢？2^19=524288，也就是说所有点可以在一个比较小的范围内用前一天推出来，于是可以定义3个转移数组:(第二维一定不能开太大，我一开始开25暴了——————)
1.A[N][20]:A从i点经过2^j天走的路程(A[i][j]=A[i][j-1]+A[f[i][j-1]][j-1])
2.B[N][20]:B从i点经过2^j天走的路程
3.f[N][20]:A,B从i点经过2^j天走到的点 (f[i)[j]=f[f[i][j-1]][j-1]；

要先预处理处走1天的结果；
然后就是暴力求解啦

总结一下，这道题就是预处理大法

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=1e5+50;

long long  x0,n,m,hs[N],l[N],r[N],fh[N],sh[N],A[N][21],B[N][21],f[N][21];
struct node
{
    long long val,id;
}a[N];

bool cmp(node x,node y)
{
    return x.val<y.val;
}

bool judge(int p,int left,int right)
{
    if(!left) return 0;
    if(!right) return 1;
    return  a[p].val-a[left].val<=a[right].val-a[p].val;
}
int check(int p,int left,int right)
{
    if(!left) return a[right].id;
    if(!right) return a[left].id;
    if(abs(a[left].val-a[p].val)>abs(a[right].val-a[p].val)) return a[right].id;
    else return a[left].id;
}


void pre_work()
{
    for(int j=1;j<=19;j++)
    for(int i=1;i<=n;i++)
    {
        f[i][j]=f[f[i][j-1]][j-1];
        A[i][j]=A[i][j-1]+A[f[i][j-1]][j-1];
        B[i][j]=B[i][j-1]+B[f[i][j-1]][j-1];
    }
}

pair<long long,long long>  get_ans(long long s,long long x)
{
    long long  a=0,b=0;
    for(int i=19;i>=0;i--)
    {
        if(f[s][i]&&(long long)(a+A[s][i]+b+B[s][i])<=x)
        {
            a+=A[s][i];
            b+=B[s][i];
            s=f[s][i];
        }
    }
    if(sh[s]&&(a+b+A[s][0])<=x) a+=A[s][0];
    return {a,b};
}
int main()
{
     cin>>n;
     for(int i=1;i<=n;i++) cin>>a[i].val,a[i].id=i;

     sort(a+1,a+1+n,cmp);

     for(int i=1;i<=n;i++)
     hs[a[i].id]=i,l[i]=i-1,r[i]=i+1;
     l[1]=r[n]=0;

    for(int i=1;i<=n;i++)      //双向链表算法
    {
        int p=hs[i];
        int left=l[p],right=r[p];

        if(judge(p,left,right)) fh[i]=a[left].id,sh[i]=check(p,l[left],right);
        else fh[i]=a[right].id,sh[i]=check(p,left,r[right]);
        if(left) r[left]=right;
        if(right) l[right]=left;
    }

    for(int i=1;i<=n;i++)
    {
        f[i][0]=fh[sh[i]];
        A[i][0]=abs(a[hs[i]].val-a[hs[sh[i]]].val);
        B[i][0]=abs(a[hs[sh[i]]].val-a[hs[fh[sh[i]]]].val);
    }

    pre_work();  //倍增

    cin>>x0>>m;
    long long  ans;
    double minn=1e9;
     for(int i = 1; i <= n; i++){
        pair<long long ,long long> tmp=get_ans(i, x0);
        if(tmp.second && 1.0*tmp.first/tmp.second < minn){
            minn = 1.0*tmp.first/tmp.second;
            ans = i;
        }
    }
    cout<<ans<<endl;
    while(m--)
    {
        long long x,start;
        cin>>start>>x;
        pair<long long ,long long> ans=get_ans(start,x);
        cout<<ans.first<<" "<<ans.second<<endl;
    }

    return 0;
}