题解 P1081 【开车旅行】

· · 题解

用的双端链表（set的话有些oj上要T啦啦啦）

预处理前缀后缀用双向链表。set常数太大，和我的暴力得分一样，；

连这玩意没听过的：BZOJ 1588营业额统计 我的题解：http://blog.csdn.NET/pbihao/article/details/52831600

至于倍增嘛，其实很简单，把小A和小B走一轮（不是哪一个）作为一个循环节，然后倍增上去，再记录倍增后小A走的路程和小B走的，其实难在求前后缀。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define LL long long
#define maxn 100020
using namespace std;
int n,m,b[maxn],toa[maxn],tob[maxn],fa[maxn][20],fb[maxn][20],f[maxn][20],h[maxn];
struct edge{
    int ls,rs,id,h;
    bool operator<(const edge& b)const{return h<b.h;}
}e[maxn];
struct Pre{
    int dis,id,h;
    Pre(int a=0,int b=0,int c=0):dis(a),id(b),h(c){}
    bool operator < (const Pre& b)const {return dis==b.dis? h<b.h : dis < b.dis;}
}t[5];
void front(){
    sort(e+1,e+1+n);
    for(int i=1;i<=n;i++){
        b[e[i].id]=i;
        if(i^1)e[i].ls=i-1;
        else e[i].ls=0;
        if(i^n)e[i].rs=i+1;
        else e[i].rs=0;
    }
    for(int i=1;i<=n;i++){
        int now=0;
        int nw=b[i],l1=e[nw].ls,l2=e[l1].ls,r1=e[nw].rs,r2=e[r1].rs;
        if(l1!=0)t[++now]=Pre(abs(e[l1].h-e[nw].h),e[l1].id,e[l1].h);
        if(l2!=0)t[++now]=Pre(abs(e[l2].h-e[nw].h),e[l2].id,e[l2].h);
        if(r1!=0)t[++now]=Pre(abs(e[r1].h-e[nw].h),e[r1].id,e[r1].h);
        if(r2!=0)t[++now]=Pre(abs(e[r2].h-e[nw].h),e[r2].id,e[r2].h);
        if(l1^0)e[l1].rs=r1;
        if(r1^0)e[r1].ls=l1;
        sort(t+1,t+1+now);
        if(now>0)tob[i]=t[1].id;
        if(now>1)toa[i]=t[2].id;
    }
}
void read(int& x){
    char c=getchar();x=0;
    int flag=1;
    for(;(c>'9'||c<'0')&&c!='-';c=getchar());
    if(c=='-')flag=-1,c=getchar();;
    for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
    x*=flag;
}
void query(int st,int x,LL& a,LL& b){
    a=0,b=0;
    for(int i=14;i>=0;i--)if(f[st][i]&&fa[st][i]+fb[st][i]<=x){
        x-=fa[st][i]+fb[st][i];
        a+=fa[st][i],b+=fb[st][i];
        st=f[st][i];
    }
    if(toa[st]==0)return ;
    int dis=abs(h[toa[st]]-h[st]);
    if(dis<=x){
        a+=dis;
    }
}
int x0;
void solve(){
    read(x0);
    LL A,B,x,y;
    int ans=0;
    for(int i=1;i<=n;i++){
        query(i,x0,A,B);
        if(!ans||(B!=0&&(A*y<B*x))){
            ans=i,x=A,y=B;
        }
    }
    printf("%d\n",ans);
    read(m);
    int s,X;
    while(m--){
        read(s),read(X);
        query(s,X,A,B);
        printf("%lld %lld\n",A,B);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        read(e[i].h);e[i].id=i;
        h[i]=e[i].h;
    }
    front();
    for(int i=1;i<=n;i++){
        int pos1=toa[i],pos2=tob[toa[i]];
        fa[i][0]=pos1 ? abs(h[pos1]-h[i]) : 0;
        fb[i][0]=pos2 ? abs(h[pos2]-h[pos1]) : 0;
        f[i][0]=pos2;
    }
    for(int j=1;j<=14;j++)
    for(int i=1;i<=n;i++)
    {
        f[i][j]= f[f[i][j-1]][j-1];
        fa[i][j] = fa[i][j-1] + fa[f[i][j-1]][j-1];
        fb[i][j] = fb[i][j-1] + fb[f[i][j-1]][j-1];
    }
    solve();
    return 0;
}