luoguP1081 开车旅行 解题报告

解题报告

luoguP1081 开车旅行

题意

有 $n$ 个城市 $(1 \le n \le 10^5)$, 呈东西方向一字排开, 城市 $i$ 的海拔为 $h[i]$, $(-10^9 \le h[i] \le 10^9)$, 两个城市 $i,j$ 之间的距离为 $|h[i]-h[j]|$.

$A,B$ 两人开车旅行, 从西向东行驶, 每天都能且只能沿着正方向从一个城市到达另一个城市, 第一天 $A$ 开车, 之后他们每天交替开车.
$A$ 的驾驶风格为每次开到离当前城市第二近的城市,
$B$ 的驾驶风格为每次开到离当前城市最近的城市.

有两个问题 :
1. 给定 $x0$, 求在行驶总距离不超过 $x0$ 的条件下, 从哪个城市出发, 能使得 $A$ 驾驶的距离 与 $B$ 驾驶的距离 之比最小.
2. 给定 $m$ 组 $s,x$ $(1 \le m \le 10^5)$, 分别代表出发的城市和行驶的最大距离, 求 $A,B$ 各自的驾驶距离.

思路

其实想到倍增的话这道题就不怎么难了 (然而我是听别人说了这道题是倍增之后再去做的....)

由于从每个城市出发, 下一次到达的城市以及经过的距离是一定的, 所以可以先预处理出每座城市往后的最近城市和次近城市,
然后再预处理出 $g[i][k],f1[i][k],f2[i][k]$, 分别表示从点 $i$ 出发, 经过 $2^k$ 座城市后到达的城市, $A$ 的行驶距离, $B$ 的行驶距离.

最近城市和次进城市我是用 set 来处理, 然后因为 STL 运用不熟练, 还调了一段时间...

总的来说这道题还算简单, 就是预处理时有一些细节还是要注意的.

代码

#include<bits/stdc++.h>
#define ll long long
#define itr iterator
#define lb lower_bound
using namespace std;
const int N=1e5+7;
const int L=20;
const ll inf=1e17;
int n,m,f[N][3],g[N][L+7];
ll h[N],s1[N][L+7],s2[N][L+7];
struct city{
    int id;
    ll h;
    bool operator < (const city x) const{ return h<x.h; }
    bool operator <= (const city x) const{ return h<=x.h; }
    bool operator > (const city x) const{ return h>x.h; }
    bool operator >= (const city x) const{ return h>=x.h; }
    bool operator == (const city x) const{ return h==x.h; }
}a[N],fs[4];
set<city> S;
int now;
bool rule(city x,city y){
    ll tx=abs(x.h-a[now].h),ty=abs(y.h-a[now].h);
    return tx==ty ?x.h<y.h :tx<ty;
}
ll dis(int x,int y){ 
    if(x==0||y==0) return 0;
    return abs(h[x]-h[y]); 
}
bool clsr(city a,city b,city x){
    ll ta=abs(a.h-x.h),tb=abs(b.h-x.h);
    if(ta==tb) return a.h<b.h;
    else return ta<tb;
}
void pre(){
    S.insert(a[n]);
    // 各种丑陋的分类讨论...
    for(int i=n-1;i>=1;i--){
        now=i;
        set<city>::itr it=S.lb(a[i]),it1,it2,it3;
        if(it!=S.begin()){ it--; it1=it; it++; }
        else it1=it;
        if(it1!=S.begin()){ it1--; it3=it1; it1++; }
        else it3=it1;
        if(it!=S.end()){ it++; it2=it; it--; }
        else{ it2=it=it1; }
        if(it2==S.end()) it2--;
        fs[1]=*it1; fs[2]=*it; fs[3]=*it2;
        city t3=*it3,t2=*it2;
        if(it3!=it1&&clsr(t3,t2,a[i])) fs[3]=*it3;
        sort(fs+1,fs+4,rule);
        if(fs[1]==fs[2]){
            if(fs[1]==fs[3]) f[i][1]=0;
            else f[i][1]=fs[3].id;
        }
        else f[i][1]=fs[2].id;
        f[i][2]=fs[1].id; 
        S.insert(a[i]);
    }
    for(int i=n;i>=1;i--){
        g[i][0]=f[i][1];
        s1[i][0]=dis(i,f[i][1]);
        g[i][1]=f[f[i][1]][2];
        s1[i][1]=dis(i,f[i][1]);
        s2[i][1]=dis(f[i][1],g[i][1]);
        for(int k=2;k<=L;k++){
            g[i][k]=g[g[i][k-1]][k-1];
            s1[i][k]=s1[i][k-1]+s1[g[i][k-1]][k-1];
            s2[i][k]=s2[i][k-1]+s2[g[i][k-1]][k-1];
        }
    }
}
void find(int s,ll x,ll &t1,ll &t2){
    t1=t2=0;
    for(int i=L;i>=0;i--)
        if(g[s][i]&&s1[s][i]+s2[s][i]<=x){
            x-=s1[s][i]+s2[s][i];
            t1+=s1[s][i];
            t2+=s2[s][i];
            s=g[s][i];
        }
}
int run(ll x0){
    int ans=0; h[0]=-inf;
    ll res1=0,res2=0,t1=0,t2=0;
    for(int i=1;i<=n;i++){
        find(i,x0,t1,t2);
        if(!t2&&res2) continue;
        if(res1*t2>t1*res2||(res1*t2==t1*res2&&h[i]>h[ans])){
            ans=i;
            res1=t1; res2=t2;
        }
    }
    return ans;
}
int main(){
//  freopen("drive1.in","r",stdin);
//  freopen("drive.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){ 
        scanf("%lld",&h[i]);
        a[i].id=i; a[i].h=h[i];
    }
    pre();
    ll x0; scanf("%lld",&x0);
    printf("%d\n",run(x0));
    cin>>m; int s; ll x,t1,t2;
    for(int i=1;i<=m;i++){
        scanf("%d%lld",&s,&x);
        find(s,x,t1,t2);
        printf("%lld %lld\n",t1,t2);
    }
    return 0;
}