NOIP2012 开车旅行

题目:

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

思路:

   在每个点小A和小B会开向的点是固定的,所以可以用set 预处理出每个点在小A或小B会开向的点,这样就能得到一个的暴力,每次就用这个数组暴力跳。再用倍增去优化这个暴力跳,每次地跳,复杂度

代码:

#include <bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof a)
#define MP make_pair
#define DEBUG(x) cerr<<"DEBUG: "<<#x<<'='<<(x)<<endl
#define ll long long
#define File(_) freopen(#_".in","r",stdin),freopen(#_".out","w",stdout)
#define MN 100005
#define inf 2100000000
using namespace std;
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
typedef pair<int,int> pii;
#define hig first
#define id second
set<pii> s;
int h[MN];
pii getFir(int x){
    pii a=*s.lower_bound(make_pair(h[x],x));
    pii b=*--s.upper_bound(make_pair(h[x],x));
    if(abs((ll)h[x]-a.hig)<abs((ll)h[x]-b.hig))
        return a;
    else
        return b;
}
pii getSec(int x){
    pii a=getFir(x);
    s.erase(a);
    pii b=getFir(x);
    s.insert(a);
    return b;
}
int to[MN][2],dis[MN][2];
void init_dis(int n){
#define add(x) s.insert(x)
    add(MP(inf,-1));add(MP(-inf,-1));
    for(int i=n;i;i--){
        pii fir=getFir(i),sec=getSec(i);
        to[i][0]=sec.id;
        dis[i][0]=abs(h[i]-sec.hig);
        to[i][1]=fir.id;
        dis[i][1]=abs(h[i]-fir.hig);
        add(MP(h[i],i));
    }
#undef add
}
ll stDis[MN][20][2];
int stTo[MN][20];
void init_st(int n){
    clr(stTo,-1);
    for(int i=1;i<=n;i++){
        int p=i;
        stDis[i][0][0]=dis[i][0];
        p=to[p][0];
        if(p>0)stDis[i][0][1]=dis[p][1];
        if(p>0)p=to[p][1];
        stTo[i][0]=p;
    }
    for(int k=1;k<=17;k++)
        for(int i=1;i<=n;i++){
            if(i+(1<<k)>n)break;
            stTo[i][k]=stTo[stTo[i][k-1]][k-1];
            stDis[i][k][0]=stDis[i][k-1][0]+stDis[stTo[i][k-1]][k-1][0];
            stDis[i][k][1]=stDis[i][k-1][1]+stDis[stTo[i][k-1]][k-1][1];
        }
}
struct Data{int a,b;};
Data calc(int s,int x){
    int num[]={0,0};
    for(int i=17;~i;i--){
        if(stTo[s][i]>0&&x>=stDis[s][i][0]+stDis[s][i][1]){
            num[0]+=stDis[s][i][0];
            num[1]+=stDis[s][i][1];
            x-=stDis[s][i][0]+stDis[s][i][1];
            s=stTo[s][i];
        }
    }
    if(to[s][0]>0&&x>=dis[s][0])num[0]+=dis[s][0];
    return (Data){num[0],num[1]};
}
int main(){
    //File(drive);
    int n,m,x,p;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",h+i);
    init_dis(n);
    init_st(n);
    scanf("%d",&x);
    Data best=(Data){1,0};
    int ans=0;
    for(int i=1;i<=n;i++){
        Data d=calc(i,x);
        if(d.b==0)d.a=1;
        if(!ans||(ll)d.a*best.b<(ll)d.b*best.a)
            best=d,ans=i;
        else if((ll)d.a*best.b==(ll)d.b*best.a&&h[i]>h[ans])
            ans=i;
    }
    cout<<ans<<endl;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&p,&x);
        Data d=calc(p,x);
        printf("%d %d\n",d.a,d.b);
    }
    return 0;
}