题解：P1081 [NOIP2012 提高组] 开车旅行

star_fish · 2025-01-14 15:12:46 · 题解

原题链接

第一道不看题解写出来的紫题。写篇题解纪念一下。

25.1.23 update：优化重写了建链表部分的代码。

大致思路：

先考虑模拟。对于每一个城市，我们可以预先处理出每一个城市向东的最近与次近点，建成一个链表。然后对于每次询问进行递归模拟，最后输出小 A 和小 B 行驶的路程。

代码实现一

先实现链表部分。

注：这部分中双指针的做法有点问题，已在后文优化。

暴力查找必定超时，我们可以先对 h 数组进行从小到大排序，对于每一个城市 x，使用双指针找出绝对值小于 x 的最近与次近城市、绝对值大于 x 的最近、次近城市。由于旅行方向向东，排序之后满足条件的城市应为数组中 x 左、右边序号小于 x 序号的城市。题面中提到对于距离相同的城市，我们应该将高度较小的当做更近的，因此我们可以按照高度顺序调用更新函数，以满足条件。

对于第一问，我们对每一个起点进行一次模拟并更新答案，最终输出最大值对应的城市。注意转 double 并且比值相同取 h 值小的。

对于第二问，我们同样对每一个问题进行模拟，输出两个答案。

这样就可以在洛谷上获得 80pts。听说可以直接跑过当年的数据而且比标程还快。

贴出我的代码，附注释。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100100
const int inf=1e17;
const double eps=1e-12;
int n,m,h[N],x[N],s[N],id[N],pos[N],to[N][2],f[N][2],ans[2],maxn,maxi;
double d=inf;
//to数组记录i后的最小值与次小值 以及前往的城市编号 
bool cmp(int x,int y){ return h[x]<h[y];}
void update(int i,int x){//更新最小值与次小值 
    if(x==0||x==n+1||x<=i) return ;
    int w=abs(h[x]-h[i]);//0为最小值,即为B要去的城市 
    if(w<=f[i][0])
        f[i][1]=f[i][0],f[i][0]=w,
        to[i][1]=to[i][0],to[i][0]=x;
    else if(w<=f[i][1]) f[i][1]=w,to[i][1]=x;   

}
void init(){
    for(int s=1;s<=n;s++){//初始化处理,建立 
        int l=pos[s],r=pos[s],R,L;
        while(l&&id[l]<=s) l--; 
        while(r<=n&&id[r]<=s) r++;   
        R=r,L=l;
        if(l){l--;while(l&&id[l]<=s) l--;}
        if(r<=n){r++;while(r<=n&&id[r]<=s) r++;}
        if(r!=R)update(s,id[r]);
        update(s,id[R]),update(s,id[L]);
        if(l!=L) update(s,id[l]);
    }
}
void check(int s,int fl,int sum){//进行模拟 
    if(!to[s][fl]||sum+f[s][fl]>maxn) return ;
    ans[fl]+=f[s][fl];
    check(to[s][fl],1-fl,sum+f[s][fl]);
    return ;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;h[0]=-inf;
    for(int i=1;i<=n;i++) 
        cin>>h[i],id[i]=i,
        f[i][0]=f[i][1]=inf,
        to[i][0]=to[i][1]=0;
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++) pos[id[i]]=i;
    init();
    cin>>maxn>>m;
    for(int i=1;i<=n;i++){
        ans[0]=ans[1]=0;
        check(i,1,0);
        if(!ans[0]&&!ans[1]) continue;
        double dd;
        if(ans[0]==0) dd=inf;
        else dd=(double)ans[1]/(double)ans[0];
        if(!maxi||dd<d) d=dd,maxi=i;
        else if(abs(dd-d)<eps&&h[i]>h[maxi]) maxi=i;
    }
    cout<<maxi<<'\n';
    for(int i=1;i<=m;i++){
        cin>>s[i]>>maxn;
        ans[0]=ans[1]=0;
        check(s[i],1,0);
        cout<<ans[1]<<' '<<ans[0]<<'\n';
    }
    return 0;
}

代码实现二（倍增优化）

接下来我们在原来的代码上用倍增加快模拟的过程。

在 to 数组中，我们使用 to_{i,0} 记录 i 城市的次近点，即小 A 走一步要去的点；用 to_{i,1} 记录城市的次近点的最近点（与上面的代码不同）。这么做的意义是将两步捆做一步，以便于后面的倍增数组更新。f 数组也是同理。与此同时，我们也要用一个额外的 fA 数组来记录总路程中小 A 走的路程，以得到答案。

这里贴出倍增代码与修改后的初始化代码。当然你也可以按照上面的思路重新写一份。

for(int i=1;i<=n;i++)
    swap(to[i][1],to[i][0]),swap(f[i][1],f[i][0]);
    //此时用to[i][0]表示次近，用to[i][1]表示最近 
for(int i=1,j;i<=n;i++){
    //在这之后，我们要用to[i][1]表示走两步 
    //即为先走一个次近,再走一个最近 
    j=to[i][0];//次近 
    f[i][1]=f[i][0]+f[j][1];
    to[i][1]=to[j][1];
    fA[i][0]=f[i][0],fA[i][1]=f[i][0];
}
for(int k=2;k<=30;k++){
    for(int i=1;i<=n;i++){
        int j=to[i][k-1];
        if(!j) continue;
        to[i][k]=to[j][k-1];
        f[i][k]=f[i][k-1]+f[j][k-1];
        fA[i][k]=fA[i][k-1]+fA[j][k-1];
    }
}

void check(int s){
    sum=0,suma=0;
    for(int k=30;k>=0;k--)
        if(to[s][k]&&sum+f[s][k]<=maxn) 
            sum+=f[s][k],suma+=fA[s][k],s=to[s][k];
    return ;
}

DLC 链表部分的优化

其实写题解的时候总是有两个点差100ms，本来以为是常数问题，卡了半天不得不承认是自己链表部分复杂度假了。因此在期末考后重新添加了后半部分题解。

在之前的链表实现中，我们通过双指针来向前和向后找下一个前往的节点。这个过程中需要在数组的左边和右边分别找两个满足条件（即编号小于 i ）的节点，可以用大根堆优化。

以找右端点为例，在遍历排序后的 id 数组时，我们用两个小根堆已经遍历过的节点，第一个小根堆记录“还没有找到第一个右端点”的节点，第二个小根堆记录“还没有找到第二个右端点”的节点。遍历到编号为 i 的节点时，通过弹出并更新堆中编号比 i 小的节点建立链表。

为了省脑子我这里等找完后再更新。

优化后的链表代码：

priority_queue<int> q,q1,p,p1;
//枚举到一个数时,将更新前面所有编号比i小的节点的右边端点 
for(int i=1;i<=n;i++){
    while(!p1.empty()&&-p1.top()<id[i]) R[-p1.top()]=id[i],p1.pop();
    while(!p.empty()&&-p.top()<id[i]) r[-p.top()]=id[i],p1.push(p.top()),p.pop();
    p.push(-id[i]);
}
//枚举到一个数时,将更新后面所有编号比i小的节点的左边端点 
for(int i=n;i>=1;i--){
    while(!q1.empty()&&-q1.top()<id[i]) L[-q1.top()]=id[i],q1.pop();
    while(!q.empty()&&-q.top()<id[i]) l[-q.top()]=id[i],q1.push(q.top()),q.pop();
    q.push(-id[i]);
}
for(int i=1;i<=n;i++){
    update(i,R[i]),update(i,r[i]);
    update(i,l[i]),update(i,L[i]);
}

AC code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100100
const int inf=1e18;
const double eps=1e-12;
int n,m,h[N],x[N],s[N],id[N],pos[N],to[N][40],f[N][40],fA[N][40],ans[2],maxn,maxi;
int sum,suma;
double d=inf;
bool cmp(int x,int y){ return h[x]<h[y];}
void update(int i,int x){//更新最小值与次小值 
    if(x==0) return ;
    int w=abs(h[x]-h[i]);//0为最小值,即为B要去的城市,走1<<0步 
    if(w<=f[i][0])// ,走1<<1步 
        f[i][1]=f[i][0],f[i][0]=w,
        to[i][1]=to[i][0],to[i][0]=x;
    else if(w<=f[i][1]) f[i][1]=w,to[i][1]=x;   

}
int R[N],L[N],l[N],r[N];
priority_queue<int> q,q1,p,p1;
void init(){
    //枚举到一个数时,将更新前面所有编号比i小的节点的右边端点 
    for(int i=1;i<=n;i++){
        while(!p1.empty()&&-p1.top()<id[i]) R[-p1.top()]=id[i],p1.pop();
        while(!p.empty()&&-p.top()<id[i]) r[-p.top()]=id[i],p1.push(p.top()),p.pop();
        p.push(-id[i]);
    }
    //枚举到一个数时,将更新后面所有编号比i小的节点的左边端点 
    for(int i=n;i>=1;i--){
        while(!q1.empty()&&-q1.top()<id[i]) L[-q1.top()]=id[i],q1.pop();
        while(!q.empty()&&-q.top()<id[i]) l[-q.top()]=id[i],q1.push(q.top()),q.pop();
        q.push(-id[i]);
    }
    for(int i=1;i<=n;i++){
        update(i,R[i]),update(i,r[i]);
        update(i,l[i]),update(i,L[i]);
    }
    for(int i=1;i<=n;i++)
        swap(to[i][1],to[i][0]),swap(f[i][1],f[i][0]);
    for(int i=1,j;i<=n;i++){
        j=to[i][0];//次近 
        f[i][1]=f[i][0]+f[j][1];
        to[i][1]=to[j][1];
        fA[i][0]=f[i][0],fA[i][1]=f[i][0];
    }
    for(int k=2;k<=30;k++){
        for(int i=1;i<=n;i++){
            int j=to[i][k-1];
            if(!j) continue;
            to[i][k]=to[j][k-1];
            f[i][k]=f[i][k-1]+f[j][k-1];
            fA[i][k]=fA[i][k-1]+fA[j][k-1];
        }
    }
}
void check(int s){
    sum=0,suma=0;
    for(int k=30;k>=0;k--)
        if(to[s][k]&&sum+f[s][k]<=maxn) 
            sum+=f[s][k],suma+=fA[s][k],s=to[s][k];
    return ;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    h[0]=-inf;
    for(int i=1;i<=n;i++) 
        cin>>h[i],id[i]=i,
        memset(f[i],0x3f,sizeof f[i]),
        memset(fA[i],0x3f,sizeof fA[i]);
    sort(id+1,id+1+n,cmp);
    init();
    cin>>maxn>>m;
    for(int i=1;i<=n;i++){
        check(i);
        ans[0]=sum-suma,ans[1]=suma;
        if(!ans[0]&&!ans[1]) continue;
        double dd;
        if(ans[0]==0) dd=inf;
        else dd=(double)ans[1]/(double)ans[0];
        if(!maxi||dd<d) d=dd,maxi=i;
        else if(abs(dd-d)<eps&&h[i]>h[maxi]) maxi=i;
    }
    cout<<maxi<<'\n';
    for(int i=1;i<=m;i++){
        cin>>s[i]>>maxn;
        check(s[i]);
        cout<<suma<<' '<<sum-suma<<'\n';
    }
    return 0;
}