codevs1199 开车旅行

【问题描述】
小 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 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
2. 对任意给定的 X=X i 和出发城市 S i ,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。
【输入】
输入文件为 drive.in。
第一行包含一个整数 N,表示城市的数目。
第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即 H 1 ,H 2 ,......,H n ,且每个 H i 都是不同的。
第三行包含一个整数 X 0 。
第四行为一个整数 M,表示给定 M 组 S i 和 X i 。
接下来的 M 行,每行包含 2 个整数 S i 和 X i ,表示从城市 S i 出发,最多行驶 X i 公里。
【输出】
输出文件为 drive.out。
输出共 M+1 行。
第一行包含一个整数 S 0 ,表示对于给定的 X 0 ,从编号为 S 0 的城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。
接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 S i 和X i 下小 A 行驶的里程总数和小 B 行驶的里程总数。
【数据范围】
对于 30%的数据,有 1≤N≤20,1≤M≤20;
对于 40%的数据,有 1≤N≤100,1≤M≤100;
对于 50%的数据,有 1≤N≤100,1≤M≤1,000;
对于 70%的数据,有 1≤N≤1,000,1≤M≤10,000;
对于 100%的数据,有 1≤N≤100,000,1≤M≤10,000,-1,000,000,000≤H i ≤1,000,000,000,0≤X 0 ≤1,000,000,000,1≤S i ≤N,0≤X i ≤1,000,000,000,数据保证 H i 互不相同。

正解：倍增+set

解题报告：

　　显然要先预处理再查找。我的做法就是先用set维护距离每个点的最近点和次近点，讨论比较复杂。。。错了几发，需要了考虑有可能最近点和次近点都是由同一个大小关系转移过来，而且相等的时候，小的更优，必须注意讨论一下。

　　不妨令g[i][j]表示i跳2^j的轮回之后可以到达的位置，一次轮回至少2个位置，所以j顶多为16。f[i][j][1]表示从点i跳过2^j个轮回之后小A走过的距离，f[i][j][0]表示从点i跳过2^j个轮回之后小B走过的距离.

　　更新很简单： 

　　 g[i][j]=g[g[i][j-1]][j-1];
        f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
        f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];

　　预处理一下g数组和f数组，到这里我第一次又写萎了一个地方，就是j的循环在外，i的在内才能保证每次计算时要用到的值都已经计算出来了。

　　之后就是两个询问。第一个询问直接for一遍，模拟的跑一下看从哪个结点出来那个比值最小，注意处理边界条件，就是有可能最后一次小A还可以再走一次。第二种询问也是一样的做法，也要讨论一下边界，因为我们是倍增的模式，所以统计的次数是log级别的，时间复杂度很对。就是代码有点长，细节多。。。

　　代码如下：

//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32   
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = 100011;
const int inf = 2147483647;
int n,m,h[MAXN],S;
LL X0,cun;
int jump[MAXN][2];//A:1 B:0
int g[MAXN][17];//2^17大于10w ，g[i][j]表示i跳2^j的轮回之后可以到达的位置，一次轮回至少2个位置，16次方即可
LL f[MAXN][17][2];//f[i][j][1]表示从点i跳过2^j个轮回之后小A走过的距离，f[i][j][0]表示从点i跳过2^j个轮回之后小B走过的距离
LL ans1,ans2;
double daan;
LL ans;
set<int>bst;
map<int,int>mp;

inline int getint()
{
       int w=0,q=0;
       char c=getchar();
       while((c<'0' || c>'9') && c!='-') c=getchar();
       if (c=='-')  q=1, c=getchar();
       while (c>='0' && c<='9') w=w*10+c-'0', c=getchar();
       return q ? -w : w;
}

inline void find_place(){
    int t; LL tong1,tong2;
    int pos; double pp; int jilu=-1;
    for(int i=1;i<=n;i++) {
    t=16; tong1=0; tong2=0; pos=i; X0=cun;
    for(;t>=0;t--) {
        if(g[pos][t]==0) continue;
        if(X0<f[pos][t][0]+f[pos][t][1]) continue;
        X0-=f[pos][t][0]+f[pos][t][1];
        tong1+=f[pos][t][0]; tong2+=f[pos][t][1];
        pos=g[pos][t];
    }
    if(X0>=f[pos][0][1]) X0-=f[pos][0][1],tong2+=f[pos][0][1];
    if(tong1==0) continue;
    pp=(double)tong2/tong1;
    if(pp<daan) daan=pp,jilu=i;
    else if(pp==daan && h[i]>h[jilu]) jilu=i;
    }
    printf("%d
",jilu);
} 

inline void go(){
    int t=16; 
    for(;t>=0;t--) {
    if(g[S][t]==0) continue;
    if(X0<f[S][t][0]+f[S][t][1]) continue;
    X0-=f[S][t][0]+f[S][t][1];
    ans1+=f[S][t][0]; ans2+=f[S][t][1];
    S=g[S][t];
    }
    if(X0>=f[S][0][1]) X0-=f[S][0][1],ans2+=f[S][0][1];
    printf("%lld %lld
",ans2,ans1);
}

inline void work(){
    n=getint(); for(int i=1;i<=n;i++) h[i]=getint();
    bst.insert(inf); bst.insert(-inf); bst.insert(h[n]);
    int ql,qr,nowl,nowr; for(int i=1;i<=n;i++) mp[h[i]]=i;
    for(int i=n-1;i>=1;i--) {
    ql=*--bst.lower_bound(h[i]); qr=*bst.lower_bound(h[i]);
    if(ql==-inf) {
        ql=*++bst.lower_bound(qr);        
        jump[i][0]=mp[qr];
        if(ql!=inf)  {
        jump[i][1]=mp[ql];
        f[i][0][0]=abs(h[ jump[jump[i][1]][0] ]-h[jump[i][1]]);
        g[i][0]=jump[jump[i][1]][0];    
        f[i][0][1]=ql-h[i];  
        }
    }
    else if(qr==inf) {
        qr=*--bst.lower_bound(ql); jump[i][0]=mp[ql];
        if(qr!=-inf) {
        jump[i][1]=mp[qr]; 
        f[i][0][0]=abs(h[ jump[jump[i][1]][0] ]-h[jump[i][1]]);
        g[i][0]=jump[jump[i][1]][0];
        f[i][0][1]=h[i]-qr; 
        }
    }
    else{
        nowl=abs(h[i]-ql); nowr=abs(h[i]-qr);
        if(nowl<nowr) {
        jump[i][0]=mp[ql]; ql=*--bst.lower_bound(ql); 
        if(ql!=-inf) {
            nowl=abs(h[i]-ql); if(nowl<=nowr) qr=ql;            
        }
        nowr=abs(qr-h[i]);
        jump[i][1]=mp[qr]; 
        g[i][0]=jump[jump[i][1]][0];
        f[i][0][1]=nowr; f[i][0][0]=abs(h[ jump[jump[i][1]][0] ]-h[jump[i][1]]);
        }
        else if(nowl==nowr) {
        jump[i][1]=mp[qr]; jump[i][0]=mp[ql];
        g[i][0]=jump[jump[i][1]][0];
        f[i][0][1]=nowr; f[i][0][0]=abs(h[ jump[jump[i][1]][0] ]-h[jump[i][1]]);
        }
        else{
        jump[i][0]=mp[qr]; qr=*++bst.lower_bound(qr); 
        if(qr!=inf) {
            nowr=abs(h[i]-qr); if(nowl>nowr)  ql=qr;
        }
        nowl=abs(ql-h[i]);
        jump[i][1]=mp[ql]; 
        g[i][0]=jump[jump[i][1]][0];
        f[i][0][1]=nowl;  f[i][0][0]=abs(h[ jump[jump[i][1]][0] ]-h[jump[i][1]]);
        }
    }
    bst.insert(h[i]);
    } 

    for(int j=1;j<=16;j++)//注意顺序！！！
    for(int i=1;i<=n;i++) {
        g[i][j]=g[g[i][j-1]][j-1];
        f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
        f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];
    }

    cun=X0=getint(); m=getint();
    daan=1e20; find_place();
    while(m--) {
    S=getint(); X0=getint();
    ans1=0; ans2=0; go();
    }
}

int main()
{
  work();
  return 0;
}