题解 | 开车旅行-NOIP2012提高组复赛F题

题目描述

小 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₀ ，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0 ，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
2.对任意给定的 X=X_i 和出发城市 S_i ，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

输入描述:

第一行包含一个整数 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$ 出发，最多行驶公里。

输出描述:

输出共 M+1 行。
第一行包含一个整数 $S_0$ ，表示对于给定的 $X_0$ ，从编号为 $S_0$ 的城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。
接下来的 M 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的 $S_i$ 和 $X_i$ 下小 A 行驶的里程总数和小 B 行驶的里程总数。

示例1

输入

4
2 3 1 4
3
4
1 3
2 3
3 3
4 3

输出

1
1 1
2 0
0 0
0 0

说明

各个城市的海拔高度以及两个城市间的距离如上图所示。
如果从城市 1 出发，可以到达的城市为 2,3,4 ，这几个城市与城市 1 的距离分别为 1,1,2 ，但是由于城市 3 的海拔高度低于城市 2 ，所以我们认为城市 3 离城市 1 最近，城市 2 离城市 1 第二近，所以小A会走到城市 2 。到达城市 2 后，前面可以到达的城市为 3,4 ，这两个城市与城市 2 的距离分别为 2,1 ，所以城市 4 离城市 2 最近，因此小B会走到城市 4 。到达城市 4 后，前面已没有可到达的城市，所以旅行结束。
如果从城市 2 出发，可以到达的城市为 3,4 ，这两个城市与城市 2 的距离分别为 2,1 ，由于城市 3 离城市 2 第二近，所以小A会走到城市 3 。到达城市 3 后，前面尚未旅行的城市为 4 ，所以城市 4 离城市 3 最近，但是如果要到达城市 4 ，则总路程为 2+3=5>3 ，所以小B会直接在城市 3 结束旅行。
如果从城市 3 出发，可以到达的城市为 4 ，由于没有离城市 3 第二近的城市，因此旅行还未开始就结束了。

示例2

输入

10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7

输出

2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

说明

当 X=7 时，如果从城市 1 出发，则路线为 1 → 2 → 3 → 8 → 9 ，小A走的距离为 1+2=3 ，小B走的距离为 1+1=2 。（在城市 1 时，距离小A最近的城市是 2 和 6 ，但是城市 2 的海拔更高，视为与城市 1 第二近的城市，所以小A最终选择城市 2 ；走到 9 后，小A只有城市 10 可以走，没有第 2 选择可以选，所以没法做出选择，结束旅行）
如果从城市 2 出发，则路线为 2 → 6 → 7 ，小A和小B走的距离分别为 2,4 。
如果从城市 3 出发，则路线为 3 → 8 → 9 ，小A和小B走的距离分别为 2,1 。
如果从城市 4 出发，则路线为 4 → 6 → 7 ，小A和小B走的距离分别为 2,4 。
如果从城市 5 出发，则路线为 5 → 7 → 8 ，小A和小B走的距离分别为 5,1 。
如果从城市 6 出发，则路线为 6 → 8 → 9 ，小A和小B走的距离分别为 5,1 。
如果从城市 7 出发，则路线为 7 → 9 → 10 ，小A和小B走的距离分别为 2,1 。
如果从城市 8 出发，则路线为 8 → 10 ，小A和小B走的距离分别为 2,0 。
如果从城市 9 出发，则路线为 9 ，小A和小B走的距离分别为 0,0 （旅行一开始就结束了）。
如果从城市 10 出发，则路线为 10 ，小A和小B走的距离分别为 0,0 。
从城市 2 或者城市 4 出发小A行驶的路程总数与小B行驶的路程总数的比值都最小，但是城市 2 的海拔更高，所以输出第一行为 2 。

备注

对于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≤100,000 , -10⁹≤H_i≤10⁹ ,0≤X₀≤10⁹ , 1≤S_i≤N,0≤X-i≤10⁹ ，数据保证 H_i 互不相同。

解答

首先，这个预处理就极其变态，要与处理出每一个点往后走A会去哪里，B会去哪里。而且还必须O(nlogn)给它跑出来，反正这就要了我好久好久的时间，还没想出来！那么我们来慎重思考一下：
1.既然要让我们这么快的时间内把一个点东边的高度最近和次近找出来，只能考虑先排序。那我们就先让它以高度为关键字排一遍序，肯定还是要记录一下原先的序号的。
2.模拟一下，如果我们要找第一个点(最西边的点)的预处理，那不就是在排完序的数组中找一下它左边两个和它右边两个再比较一下找出最近和次近(这个应该不难想)。然后，如果再找第二个点的预处理，第一个点显然有可能会干扰到它，所以处理完第一个点之后我们考虑把它“删”掉，这就可以用双向链表来维护了(啦啦啦！别以为这个东西很NB，其实就是用一个l，r来记录i点排序之后左边和右边的第一个东边城市，啦啦啦！)，实现还是很困难的//...冷笑...\\
对应Prepare(双向链表部分在solve()里面)函数！！！
3.预处理完我们就要维护x范围内的a开的距离和b开的距离了。其实我是想了很久之后才知道怎么用倍增的(当然是看的标签之后才知道要用倍增的(我太菜了！！！))。不管了，直接倍增吧...
f[i][j]表示从i城市出发走 $2\times2^j$ (就是a，b都走 $2^j$ )步到达的城市编号。
disA[i][j]表示从i城市出发走 $2\times2^j$ (就是a，b都走 $2^j$ )步a开了多远。
disB[i][j]表示从i城市出发走 $2\times2^j$ (就是a，b都走 $2^j$ )步b开了多远。
对应Bz函数！！！最后倍增的查找对应getab函数！！！
4.一个小细节：因为我们是直接倍增跳a，b一起开(如上j)，所以找a，b各走了多远时最后还要特判一下a是否还可以在开一轮。
上代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#define lst long long
#define rg register
#define N 100050
#define Inf 2147483647
using namespace std;

int n,m,X0,ans=n;
struct CITY{
    lst v;
    int num,l,r;
}ljl[N];
int back[N],go[N],nA[N],nB[N];
int f[N][20];
lst disA[N][20],disB[N][20],a,b;
double minn=2147483647;

inline lst read()
{
    rg lst s=0,m=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')m=-1,ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return s*m;
}

inline int cmp(rg const CITY &a,rg const CITY &b){return a.v<b.v;}
inline int dis(rg int p,rg int q){return abs(ljl[p].v-ljl[q].v);}

inline int pd(rg int x,rg int y,rg int now)//x小返回1,y小返回0
{
    if(!x)return 0;//x不存在
    if(!y)return 1;//y不存在
    return dis(x,now)<=dis(y,now);//返回小一些的
}

inline void solve(rg int tt,rg int now)
{
    rg int ll=ljl[now].l,rr=ljl[now].r;
    if(pd(ll,rr,now))//左边离得近一些
        if(pd(ljl[ll].l,rr,now))//左边的左边离得近一些
            nB[tt]=back[ll],nA[tt]=back[ljl[ll].l];
        else//右边离得近一些
            nB[tt]=back[ll],nA[tt]=back[rr];
    else//右边离得近一些
        if(pd(ll,ljl[rr].r,now))//左边离得近一些
            nB[tt]=back[rr],nA[tt]=back[ll];
        else//右边的右边离得近一些
            nB[tt]=back[rr],nA[tt]=back[ljl[rr].r];
    if(ll)ljl[ll].r=rr;
    if(rr)ljl[rr].l=ll;
}

inline void Prepare()
{
    n=read();
    for(rg int i=1;i<=n;++i)ljl[i].v=read(),ljl[i].num=i;
    sort(ljl+1,ljl+n+1,cmp);//以高度为关键字排序
    for(rg int i=1;i<=n;++i)back[i]=ljl[i].num,go[back[i]]=i;//排完序之后的元素在原数组中的位置
    for(rg int i=1;i<=n;++i)ljl[i].l=i-1,ljl[i].r=i+1;
    ljl[1].l=ljl[n].r=0;
    for(rg int i=1;i<=n;++i)solve(i,go[i]);
}

inline void Bz()
{
    for(rg int i=1;i<=n;++i)
    {
        f[i][0]=nB[nA[i]];
        disA[i][0]=dis(go[i],go[nA[i]]);
        disB[i][0]=dis(go[nA[i]],go[f[i][0]]);
    }
    for(rg int j=1;j<=19;++j)
        for(rg int i=1;i<=n;++i)
        {
            f[i][j]=f[f[i][j-1]][j-1];
            disA[i][j]=disA[i][j-1]+disA[f[i][j-1]][j-1];
            disB[i][j]=disB[i][j-1]+disB[f[i][j-1]][j-1];
        }
/*    for(rg int i=1;i<=n;++i)
        for(rg int j=0;j<=3;++j)
        {
            printf("   f[%d][%d]=%d\n",i,j,f[i][j]);
            printf("disA[%d][%d]=%lld\n",i,j,disA[i][j]);
            printf("disB[%d][%d]=%lld\n",i,j,disB[i][j]);
        }
*/}

inline void getab(rg int x,rg int now)
{
    a=b=0;
    for(rg int i=19;i>=0;--i)
        if(f[now][i]&&(a+b+disA[now][i]+disB[now][i]<=x))
            a+=disA[now][i],b+=disB[now][i],now=f[now][i];
    if(nA[now]&&a+b+disA[now][0]<=x)a+=disA[now][0];
}

int main()
{
    Prepare();//预处理左右A,B的方案
//    for(rg int i=1;i<=n;++i)printf("nA[%d]=%d nB[%d]=%d\n",i,nA[i],i,nB[i]);
    Bz();//处理倍增
    X0=read(),m=read();
    for(rg int i=1;i<=n;++i)
    {
        getab(X0,i);
        if(b&&1.0*a/b<minn)
            minn=1.0*a/b,ans=i;
    }
    printf("%d\n",ans);
    for(rg int i=1;i<=m;++i)
    {
        rg int s=read(),x=read();
        getab(x,s);
        printf("%lld %lld\n",a,b);
    }
    return 0;
}

来源：eternal风度