【洛谷P1081】开车旅行【链表，倍增】

本文主要是介绍【洛谷P1081】开车旅行【链表，倍增】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

题目链接

分析

感觉这题有紫啊。

朴素的思路，预处理路程，暴力枚举会到那个城市，然后直接模拟整个过程。显然超时，复杂度 $O((n+m)*n^2)$ 。

换思路，首先，可以发现，对于某个已知的城市，且已经确定是小A/小B开车，那下一步的终点城市是唯一的。而且无论哪个询问，只要能在规定时间内求出以 $s_i$ 为起点，路程不超过 $x_i$ 公里的终点和两个人的行驶路程就行。

考虑怎么优化算法， $m$ 这一维没法优化，考虑优化成 $l o g n$ 级别的，考虑倍增。想想就能发现，先由小A/小B开车，开若干次车，有唯一的终点，且最多开n次车。所以设 $f [0/1] [i] [j]$ 表示从城市 $i$ 出发，由小A/小B先开车，开 $2^j$ 次车所到达的终点， $d i s [0/1] [i] [j]$ 表示从城市 $i$ 出发，开 $2^j$ 次车，小A/小B开车的路程。有转移方程：
$\left\{ \begin{aligned} f[0][i][j]&=f[0][f[0][i][j-1]][j-1]\\ dis[0][i][j]&=dis[0][i][j-1]+dis[0][f[0][i][j-1]][j-1] \\ dis[1][i][j]&=dis[1][i][j-1]+dis[1][f[0][i][j-1]][j-1] \end{aligned} \right.$
$特别地,当j=1时,有\left\{ \begin{aligned} f[0][i][1]&=f[1][f[0][i][0]][0];\\ dis[0][i][1]&=dis[0][i][0]; \\ dis[1][i][1]&=dis[1][f[0][i][0]][0]; \end{aligned} \right.$
当 $j = 0$ 时，我们要对两个数组进行预处理。将城市按照高度升序排序，然后建立双向链表， $l_i,r_i$ 指针分别表示按照给出顺序数第 $i$ 个城市排序后在他前面/后面的那个城市，也就是比这个城市低和高的第一个城市。

不难发现，第 $i$ 个城市下一步的目的地，一定是 $l_i,r_i,l_{l_i},r_{r_i}$ 当中的其中之一，只要枚举四个城市，看看哪个是小A/小B开车的到达地即可。但是有个限制：只能往东边走，但是这四个城市可能有在 $i$ 城市西边的。这时候就需要按照输入的时候的顺序枚举 $i$ ，然后每次按照上述方式求出 $f [1] [i] [0], d i s [1] [i] [0], f [0] [i] [0], d i s [0] [i] [0]$ ，然后把这个城市从链表中删去，就可以保证后面城市绝对不会走到他这里。删去的操作只需要将 $r [l [i]] = r [i], l [r [i]] = l [i]$ ，中间那个就被删去了。

到这里就完成了预处理部分。

查询答案的时候，对于子任务2，利用倍增的思想，从大到小枚举 $i$ ，看现在还能不能开 $2^i$ 次车，然后分别记录开车距离，更新走到的城市，这个跟求LCA有点像。对于子任务1，枚举出发城市，每次用距离算比值就行。这样总的时间复杂度就是 $O ((n + m) l o g n)$ 。

上代码

~~写了一年多啊这道题终于过了TwT。~~

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;struct node
{ll h,p;
}a[100010],b[100010];const ll inf=0x7ffffffffffff;
int n,m,x0;
ll l[100010],r[100010];
int s[100010],x[100010];
ll f[2][100010][23],dis[2][100010][23];
ll disa,disb;
double ans,mn=2147483647,mnp;inline int cmp(node l,node r) {return l.h<r.h;}void solve(int s,int x)//s出发，最多走x的处理 
{disa=disb=0;for(int i=20;i>=0;i--){if(f[0][s][i]&&x>=dis[0][s][i]+dis[1][s][i])//能开就开 {disa+=dis[0][s][i];disb+=dis[1][s][i];x-=(dis[0][s][i]+dis[1][s][i]);s=f[0][s][i];}}return;
}int main()
{cin>>n;for(int i=1;i<=n;i++){scanf("%lld",&a[i].h);a[i].p=i;b[i].h=a[i].h;b[i].p=i;}sort(b+1,b+n+1,cmp);//替换一个数组 l[1]=r[n]=0;for(int i=1;i<=n;i++)//双向链表 {l[b[i].p]=b[i-1].p;r[b[i].p]=b[i+1].p;}for(int i=1;i<=n;i++)//保证按输入顺序枚举(只走东边) {/*求差值的最小值次小值及其编号 */ ll fir,firp,sec,secp,tmp[5];fir=sec=inf/20,firp=secp=0;if(l[l[i]]) tmp[1]=a[i].h-a[l[l[i]]].h;else tmp[1]=inf/2;if(l[i]) tmp[2]=a[i].h-a[l[i]].h;else tmp[2]=inf/2;if(r[i]) tmp[3]=a[r[i]].h-a[i].h;else tmp[3]=inf/2;if(r[r[i]]) tmp[4]=a[r[r[i]]].h-a[i].h;else tmp[4]=inf/2;/*------处理小A和小B的第一步(次小,最小)-------*/ for(int j=2;j<=3;j++) if(tmp[j]<fir) fir=tmp[j],firp=j;if(firp==2) f[1][i][0]=l[i];if(firp==3) f[1][i][0]=r[i];for(int j=1;j<=4;j++) if(j!=firp&&tmp[j]<sec) sec=tmp[j],secp=j;if(secp==1) f[0][i][0]=l[l[i]];if(secp==2) f[0][i][0]=l[i];if(secp==3) f[0][i][0]=r[i];if(secp==4) f[0][i][0]=r[r[i]];if(f[1][i][0]) dis[1][i][0]=fir;//第一步的距离 if(f[0][i][0]) dis[0][i][0]=sec;/*--顺序删去链表的西边城市--*/ if(l[i]) r[l[i]]=r[i];if(r[i]) l[r[i]]=l[i];}for(int i=1;i<=n;i++)//第一步，j=0的初值 {f[0][i][1]=f[1][f[0][i][0]][0];dis[0][i][1]=dis[0][i][0];dis[1][i][1]=dis[1][f[0][i][0]][0];}for(int i=1;i<=n;i++) dis[1][i][0]=0;//第一步一定小A开 /*-------倍增数组预处理-------*/for(int j=2;j<=20;j++){for(int i=1;i<=n;i++){f[0][i][j]=f[0][f[0][i][j-1]][j-1];dis[0][i][j]=dis[0][i][j-1]+dis[0][f[0][i][j-1]][j-1];dis[1][i][j]=dis[1][i][j-1]+dis[1][f[0][i][j-1]][j-1];}}cin>>x0;cin>>m;for(int i=1;i<=m;i++) scanf("%d%d",&s[i],&x[i]);for(int i=1;i<=n;i++){solve(i,x0);ans=(double)disa/(double)disb; if(ans<mn) mn=ans,mnp=i;}cout<<mnp<<endl;for(int i=1;i<=m;i++){solve(s[i],x[i]);cout<<disa<<' '<<disb<<endl;}return 0;
}