题目分析

这题 70 分暴力很 easy… 正解有点难想… 但是比较容易理解… 可是代码比较难打…

work1

我们可以预处理从每一个城市出发小 A 和小 B 分别到的下一城市。
怎么处理？排序后用双向链表即可。很显然，若当前城市为 x, 那么排序后，小 A 和小 B 分别到的城市只用在 x+1,x+2,x-1,x-2 中找即可。每次搞事完毕后从链表中删除当前节点即可保证找的下一城市一定在当前城市后面。

int n,m;
int pos[N],f[N][21],fir[N],se[N];
LL kh[N],aa[N][21],bb[N][21];
struct node{int id,pre,nxt;LL h;}a[N];
bool cmp(node x,node y){return x.h<y.h;}
void gs(int x,int y){
    LL kl=abs(kh[x]-a[y].h),f1=abs(kh[fir[x]]-kh[x]),s1=abs(kh[se[x]]-kh[x]);
    if(!fir[x]||kl<f1)se[x]=fir[x],fir[x]=a[y].id;
    else if(!se[x]||kl<s1)se[x]=a[y].id;
}
void work1(){
    int i,x;
    for(i=1;i<=n;++i) a[i].h=read(),a[i].id=i,kh[i]=a[i].h;
    sort(a+1,a+1+n,cmp);
    for(i=1;i<=n;++i)pos[a[i].id]=i;
    for(i=1;i<=n;++i){
        if(i!=1)a[i].pre=i-1;
        if(i!=n)a[i].nxt=i+1;
    }
    for(i=1;i<=n;++i){
        x=pos[i];
        if(a[a[x].pre].pre)gs(i,a[a[x].pre].pre);
        if(a[x].pre)gs(i,a[x].pre);
        if(a[x].nxt)gs(i,a[x].nxt);
        if(a[a[x].nxt].nxt)gs(i,a[a[x].nxt].nxt);
        if(a[x].nxt)a[a[x].nxt].pre=a[x].pre;
        if(a[x].pre)a[a[x].pre].nxt=a[x].nxt;
    }
}

work2

直接模拟会 TLE，想到 log 优化，就用倍增。
我们令 “一轮” 的定义为小 A 和小 B 各开一次车。
f(i,j) 表示在 i 节点上走 $2^j$轮到达的位置，aa(i,j) 走 $2^j$轮小 A 开的路程，bb(i,j) 表示小 B 开的路程。
然后把这些数组预处理好…..

void work2(){
    int i,j;
    for(i=1;i<=n;++i){
        f[i][0]=fir[se[i]];
        if(se[i])aa[i][0]=abs(kh[se[i]]-kh[i]);
        if(f[i][0])bb[i][0]=abs(kh[f[i][0]]-kh[se[i]]);
    }
    for(j=1;j<=20;++j)
        for(i=1;i<=n;++i){
        f[i][j]=f[f[i][j-1]][j-1];
        aa[i][j]=aa[i][j-1]+aa[f[i][j-1]][j-1];
        bb[i][j]=bb[i][j-1]+bb[f[i][j-1]][j-1];
    }
}

work3

然后求答案啦。第一问枚举出发城市，第二问直接模拟即可。使用倍增思想完成。注意走了若干轮后，还要看小 A 能不能多走一次。

void getjs(int &x,LL &jsa,LL &jsb,LL &len){
    for(int i=20;i>=0;--i)
        if(f[x][i]&&aa[x][i]+bb[x][i]<=len){
        len-=aa[x][i]+bb[x][i];
        jsa+=aa[x][i],jsb+=bb[x][i],x=f[x][i];
    }
    if(se[x]&&abs(kh[se[x]]-kh[x])<=len)jsa+=abs(kh[se[x]]-kh[x]);
}
void work3(){//询问 1
    db bz=LLONG_MAX;
    int i,x,j,ans;LL len,que,jsa,jsb;
    que=read();
    for(i=1;i<=n;++i){
        len=que,x=i,jsa=jsb=0,getjs(x,jsa,jsb,len);
        db kl;
        if(!jsb)kl=LLONG_MAX;
        else kl=jsa*1.0/jsb*1.0;
        if(kl<bz)bz=kl,ans=i;
        else if(fabs(kl-bz)<1e-10&&kh[ans]<kh[i])ans=i;
    }
    printf("%d\n",ans);
}
void work4(){//询问 2
    int m,i,x;LL len,jsa,jsb;
    m=read();
    while(m--){
        x=read(),len=read(),jsa=jsb=0,getjs(x,jsa,jsb,len);
        printf("%lld %lld\n",jsa,jsb);
    }
}

题外话

代码模块化很重要。我打代码时调试 work1 调试了 40 分钟，其他模块都没有调很久。所以我就对错误位置有准确定位。否则这题可以调试到死……
还有好久没有人在 k-xzy 里写题解了……

总代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
#include<cmath>
using namespace std;
#define LL long long
#define db double
LL read(){
    LL q=0,w=1;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+(LL)(ch-'0'),ch=getchar();
    return q*w;
}
const int N=100005;
int n,m;
int pos[N],f[N][21],fir[N],se[N];
LL kh[N],aa[N][21],bb[N][21];
struct node{int id,pre,nxt;LL h;}a[N];
bool cmp(node x,node y){return x.h<y.h;}
void gs(int x,int y){
    LL kl=abs(kh[x]-a[y].h),f1=abs(kh[fir[x]]-kh[x]),s1=abs(kh[se[x]]-kh[x]);
    if(!fir[x]||kl<f1)se[x]=fir[x],fir[x]=a[y].id;
    else if(!se[x]||kl<s1)se[x]=a[y].id;
}
void work1(){//链表预处理下一城市
    int i,x;
    for(i=1;i<=n;++i) a[i].h=read(),a[i].id=i,kh[i]=a[i].h;
    sort(a+1,a+1+n,cmp);
    for(i=1;i<=n;++i)pos[a[i].id]=i;
    for(i=1;i<=n;++i){
        if(i!=1)a[i].pre=i-1;
        if(i!=n)a[i].nxt=i+1;
    }
    for(i=1;i<=n;++i){
        x=pos[i];
        if(a[a[x].pre].pre)gs(i,a[a[x].pre].pre);
        if(a[x].pre)gs(i,a[x].pre);
        if(a[x].nxt)gs(i,a[x].nxt);
        if(a[a[x].nxt].nxt)gs(i,a[a[x].nxt].nxt);
        if(a[x].nxt)a[a[x].nxt].pre=a[x].pre;
        if(a[x].pre)a[a[x].pre].nxt=a[x].nxt;
    }
}
void work2(){//预处理 f,aa,bb
    int i,j;
    for(i=1;i<=n;++i){
        f[i][0]=fir[se[i]];
        if(se[i])aa[i][0]=abs(kh[se[i]]-kh[i]);
        if(f[i][0])bb[i][0]=abs(kh[f[i][0]]-kh[se[i]]);
    }
    for(j=1;j<=20;++j)
        for(i=1;i<=n;++i){
        f[i][j]=f[f[i][j-1]][j-1];
        aa[i][j]=aa[i][j-1]+aa[f[i][j-1]][j-1];
        bb[i][j]=bb[i][j-1]+bb[f[i][j-1]][j-1];
    }
}
void getjs(int &x,LL &jsa,LL &jsb,LL &len){
    for(int i=20;i>=0;--i)
        if(f[x][i]&&aa[x][i]+bb[x][i]<=len){
        len-=aa[x][i]+bb[x][i];
        jsa+=aa[x][i],jsb+=bb[x][i],x=f[x][i];
    }
    if(se[x]&&abs(kh[se[x]]-kh[x])<=len)jsa+=abs(kh[se[x]]-kh[x]);
}
void work3(){//询问 1
    db bz=LLONG_MAX;
    int i,x,j,ans;LL len,que,jsa,jsb;
    que=read();
    for(i=1;i<=n;++i){
        len=que,x=i,jsa=jsb=0,getjs(x,jsa,jsb,len);
        db kl;
        if(!jsb)kl=LLONG_MAX;
        else kl=jsa*1.0/jsb*1.0;
        if(kl<bz)bz=kl,ans=i;
        else if(fabs(kl-bz)<1e-10&&kh[ans]<kh[i])ans=i;
    }
    printf("%d\n",ans);
}
void work4(){//询问 2
    int m,i,x;LL len,jsa,jsb;
    m=read();
    while(m--){
        x=read(),len=read(),jsa=jsb=0,getjs(x,jsa,jsb,len);
        printf("%lld %lld\n",jsa,jsb);
    }
}
int main(){n=read();work1(),work2(),work3(),work4();return 0;}