[vijos1780][NOIP2012]开车旅行

Description

小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为\(H_i\)，城市\(i\)和城市\(j\)之间的距离\(d[i,j]\)恰好是这两个城市海拔高度之差的绝对值，即\(d[i,j] = |H_i - H_j|\)。
旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶\(X\)公里就结束旅行。小A和小B的驾驶风格不同，小B总是沿着前进方向选择一个最近的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出\(X\)公里，他们就会结束旅行。
在启程之前，小A想知道两个问题：
1．对于一个给定的\(X=X_0\)，从哪一个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小（如果小B的行驶路程为\(0\)，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

1. 对任意给定的\(X=X_i\) 和出发城市\(S_i\)，小A开车行驶的路程总数以及小B行驶的路程总数。

HINT

\(1≤N≤10^5，1≤M≤10^4，-10^9≤H_i≤10^9，0≤X_0≤10^9，1≤S_i≤N，0≤X_i≤10^9\)，保证\(H_i\)互不相同.

Solution

预处理出从每个城市出发距离第一小和第二小的城市.
\(f[i][j]\)表示从\(i\)出发,走\(2^j\)轮到达的城市.
\(g1[i][j]\)表示从\(i\)出发,走\(2^j\)轮小A走的路程.
\(g2[i][j]\)表示从\(i\)出发,走\(2^j\)轮小B走的路程.
倍增求解即可.

#define K 18
#define N 100005
#define INF 1000000005
typedef long long ll;
struct city{
    int h,x;
}h[N];
int f[N][K],g1[N][K],g2[N][K],nxt1[N],nxt2[N],n,m;
set s;
set::iterator xx;
bool operator < (city x,city y){
    if(x.h!=y.h) return x.h=0&&g1[u][i]+g2[u][i]>x;--i);
        if(i<0) return;
        x-=(g1[u][i]+g2[u][i]);
        d1+=g1[u][i];d2+=g2[u][i];
        u=f[u][i];
    }
}
inline bool cmp2(int j,int k,int d1,int d2,int i,int id){
    if(d1<0) return true;
    if(d2&&k) return 1ll*j*d2<1ll*d1*k||(1ll*j*d2==1ll*d1*k&&h[i].h>h[id].h);
    if(d2||k) return k;
    return h[i].h>h[id].h;
}
inline void Aireen(){
    n=read();
    for(int i=1;i<=n;++i)
        h[i].h=-read(),h[i].x=i;
    city c1,c2;
    s.clear();
    for(int i=n-1;i;--i){
        s.insert(h[i+1]);
        c1=(*s.upper_bound(h[i]));
        if(s.count(c1)){
            s.erase(c1);
            c2=(*s.upper_bound(h[i]));
            s.insert(c1);
            nxt1[i]=c1.x;nxt2[i]=c2.x;
        }
        else continue;
    }
    
    s.clear();
    for(int i=1;i<=n;++i)
        h[i].h=-h[i].h;
    for(int i=n-1;i;--i){
        s.insert(h[i+1]);
        c1=(*s.upper_bound(h[i]));
        
        if(s.count(c1)){
            s.erase(c1);
            c2=(*s.upper_bound(h[i]));
            s.insert(c1);
            if(cmp(i,c1.x,nxt1[i])){
                nxt2[i]=nxt1[i];
                nxt1[i]=c1.x;
                if(s.count(c2)&&cmp(i,c2.x,nxt2[i]))
                    nxt2[i]=c2.x; 
            }
            else if(cmp(i,c1.x,nxt2[i]))
                nxt2[i]=c1.x; 
        }
        else continue;
    }
     
    for(int j=0;jINF) g1[i][j]=INF;
            g2[i][j]=g2[i][j-1]+g2[f[i][j-1]][j-1];
            if(g2[i][j]>INF) g2[i][j]=INF;
        }
    }
    
    int u,x,d1=-1,d2,id;
    x=read();
    for(int i=1,j,k;i<=n;++i){
        drive(i,x,j,k);
        if(cmp2(j,k,d1,d2,i,id)) d1=j,d2=k,id=i;
    }
    printf("%d\n",id);
    
    m=read();
    while(m--){
        u=read();x=read();
        drive(u,x,d1,d2);
        printf("%d %d\n",d1,d2);
    }
}

2017-10-27 13:30:24