YBT高效进阶4.6.2洛谷P1081开车旅行(最详细)

YBT高效进阶 4.6.2 洛谷P1081 开车旅行
TITLE

题目描述

小A和小B决定利用假期外出旅行，他们将想去的城市从1到n编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为h_i城市i和城市j之间的距离d_{i,j},恰好是这两个城市海拔高度之差的绝对值，即





d



i


,


j




=


∣



h


i



−



h


j



∣



d_{i,j}=|h_i-h_j|


di,j​=∣hi​−hj​∣
旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市s作为起点，一直向东行驶，并且最多行驶x公里就结束旅行。
小 A 和小B的驾驶风格不同，小B 总是沿着前进方向选择一个最近的城市作为目的地，而小A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 x 公里，他们就会结束旅行。

在启程之前，小 A 想知道两个问题：

1、 对于一个给定的




x


=



x


0




x=x_0


x=x0​，从哪一个城市出发，小 A 开车行驶的路程总数与小B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

2、对任意给定的




x


=



x


i



和


出


发


城


市



s


i




x=x_i和出发城市s_i


x=xi​和出发城市si​小 \text{A}A 开车行驶的路程总数以及小 \text BB 行驶的路程总数。

输入格式

第一行包含一个整数 n，表示城市的数目。

第二行有 n个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 n 的海拔高度，即





h


1



,



h


2



.


.


.



h


n




h_1,h_2 ... h_n


h1​,h2​...hn​ ，且每个





h


i




h_i


hi​ 都是互不相同的。

第三行包含一个整数





x


0




x_0


x0​

第四行为一个整数 m，表示给定 m 组





s


i



和



x


i



x



s_i和x_ix


si​和xi​x

接下来的 m 行，每行包含 2 个整数





s


i



和



x


i




s_i和x_i


si​和xi​ ，表示从城市





s


i




s_i


si​ 出发，最多行驶





x


i




x_i


xi​ 公里。

输出格式

输出共 m+1 行。

第一行包含一个整数





s


0




s_0


s0​，表示对于给定的





x


0




x_0


x0​，从编号为





s


0




s_0


s0​ 的城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。

接下来的 m 行，每行包含 2 个整数，之间用一个空格隔开，依次表示在给定的





s


i



和



x


i




s_i和x_i


si​和xi​ 下小 A 行驶的里程总数和小 B 行驶的里程总数。

输入输出样例

输入 #1复制

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


输出 #1复制

1
1 1
2 0
0 0
0 0


输入 #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复制

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


说明/提示

【样例1说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市 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，这两个城市与城市 22 的距离分别为 2,1，由于城市 3 离城市 2 第二近，所以小 A 会走到城市 3。到达城市 3 后，前面尚未旅行的城市为 4，所以城市 4 离城市 3 最近，但是如果要到达城市 4，则总路程为 2+3=5>3，所以小 B 会直接在城市 3 结束旅行。

如果从城市 33 出发，可以到达的城市为 44，由于没有离城市 33 第二近的城市，因此旅行还未开始就结束了。

如果从城市 44 出发，没有可以到达的城市，因此旅行还未开始就结束了。

【样例2说明】

当 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→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


；



对于 30\%的数据，有1\le n \le 20,1\le m\le 20；


对于30%的数据，有1≤n≤20,1≤m≤20；





对


于


40


%


的


数


据


，


有


1


≤


n


≤


100


,


1


≤


m


≤


100


；



对于40\%的数据，有1\le n \le 100,1\le m\le 100；


对于40%的数据，有1≤n≤100,1≤m≤100；





对


于


50


%


的


数


据


，


有


1


≤


n


≤


100


,


1


≤


m


≤


1000


；



对于 50\%的数据，有1\le n \le 100,1\le m\le 1000；


对于50%的数据，有1≤n≤100,1≤m≤1000；





对


于


70


%


的


数


据


，


有


1


≤


n


≤


1000


,


1


≤


m


≤


1



0


4




对于 70\%的数据，有1\le n \le 1000,1\le m\le 10^4


对于70%的数据，有1≤n≤1000,1≤m≤104





于


100


%


的


数


据


：


1


≤


n


,


m


≤


1



0


5



,


−


1



0


9



≤



h


i



≤


1



0


9



,


1


≤



s


i



≤


n


,


0


≤



x


i



≤


1



0


9



，


数


据


保


证



h


i



​


互


不


相


同


。



于 100\%的数据：1\le n,m \le 10^5,-10^9 \le h_i≤10^9,1 \le s_i \le n,0 \le x_i \le 10^9，数据保证 h_i​互不相同。


于100%的数据：1≤n,m≤105,−109≤hi​≤109,1≤si​≤n,0≤xi​≤109，数据保证hi​​互不相同。

记得开long long
YBT高效进阶，这是我最后做的一题，这题我做了整整半天多

两点间找最优点

先比较距离
若距离都为INF,无解
若距离相当，判海拔，
若距离不相等，判距离
不要忘记判断无解(没有最优点)

if(dx==INF&&dy==INF)return 0;//无解


我因为漏了这句，调了两个多小时

long long cmp(long long x,long long y,long long dx,long long dy)//两个点找最优,x,y点id,dx,dy到正在找的点的距离
{
if(dx==INF&&dy==INF)return 0;//无解
if(dx==dy)//距离相等
{
if(h[x] return y;
}
if(dx return y;
}


小A目的地计算

因为排好了序，要找周围4个点的次优值
先算出周围两个点的最优点
判4个点时，不能是最优点
再剩下的点里找最优点
可以分治，先找左边，再找右边，再合并
注意判点是否存在
注意要判断找到的点是否存在

if(lw)dislw=abs(h[lw]-h[x]);//计算距离
if(rw)disrw=abs(h[rw]-h[x]);


我因为漏了这两句，调了一个多小时

long long cmp_four(long long x)
{
long long ld,rd,lld,rrd,lw,rw,dislw,disrw,w=cmp_two(x);
ld=lld=rd=rrd=dislw=disrw=INF;
if(l[x]&&l[x]!=w)ld=abs(h[x]-h[l[x]]);//不为最小值，计算左右距离
if(r[x]&&r[x]!=w)rd=abs(h[x]-h[r[x]]);
if(l[l[x]])lld=abs(h[l[l[x]]]-h[x]);
if(r[r[x]])rrd=abs(h[r[r[x]]]-h[x]);
lw=cmp(l[l[x]],l[x],lld,ld);//计算左边2个点的最优位置
rw=cmp(r[r[x]],r[x],rrd,rd);//计算右边2个点的最优位置
if(lw)dislw=abs(h[lw]-h[x]);//计算距离
if(rw)disrw=abs(h[rw]-h[x]);
return cmp(lw,rw,dislw,disrw);//计算最优点
}


小B目的地计算

因为排好了序，找周围两个点的最优点
注意判点是否存在

long long cmp_two(long long x)
{
long long disl=INF,disr=INF;
if(l[x])disl=abs(h[l[x]]-h[x]);//计算左右距离
if(r[x])disr=abs(h[r[x]]-h[x]);
return cmp(l[x],r[x],disl,disr);
}


预处理

预处理出从任意一个点出发，A\B走一步的目的点及路程

题目要求：
1.AB不同的驾驶风格
A走次近点
B走最近点
2.一直从西往东走

为了满足1，先排序，
最近点在周围2个点中
次近点在周围4个点中

为了满足2，用双向链表
先按排序后的顺序建表
最近点：l[x],r[x]
次近点：l[l[x]],l[x],r[x],r[r[x]]
从编号小的点枚举到编号大的点（自西先东）
每次计算完一个点
就把当前点删除
以后就无法访问该点
保证一直向东开

void work()
{
long long i;
sort(city+1,city+1+n,sortcmp);//排序
for(i=1; i<=n; ++i)l[city[i].id]=city[i-1].id,r[city[i].id]=city[i+1].id;//双向链表
for(i=1; i<=n; ++i)
{
fb[i]=cmp_two(i);//左右找最小
disb[i][0]=abs(h[i]-h[fb[i]]);
fa[i][0]=cmp_four(i);//周围四个找次小
disa[i][0]=abs(h[i]-h[fa[i][0]]);
if(l[i])r[l[i]]=r[i];//删除当前点
if(r[i])l[r[i]]=l[i];//保证一直向东走
}
return;
}


DP

设
fa[i][j]表示从i出发走2^j步的目的点(不论AB谁走)
fb[i]表示B从i出发走1步的目的点
disa[i][j]表示从i走2^j步过程中A走的路程
disb[i][j]表示从i走2^j步过程中B走的路程
用倍增优化，计算出值

void DP()
{
long long i,j;
for(i=1; i<=n; i++)//预处理AB各走一次的值
{
fa[i][1]=fb[fa[i][0]];//fa[i][j]表示从i走2^j步到达的点(不管AB走)
disa[i][1]=disa[i][0];//disa[i][j]表示从i走2^j步过程中A走的路程
disb[i][1]=disb[fa[i][0]][0];//disb[i][j]表示从i走2^j步过程中B走的路程
}
for(j=2; j<=mxm; ++j)//根据预处理,计算AB走2^j次的值
for(i=1; i<=n; ++i)//倍增
{
fa[i][j]=fa[fa[i][j-1]][j-1];
disa[i][j]=disa[i][j-1]+disa[fa[i][j-1]][j-1];
disb[i][j]=disb[i][j-1]+disb[fa[i][j-1]][j-1];
}
return;
}


用倍增计算出AB走的路程

先求出AB一起可以走多远(AB交替走,AB走的次数相同)
最后特判，如果A还能再走一次，A就再走一次

pair solve(long long s,long long x)
{
long long i;
pair ans;
for(ans.first=ans.secOnd=0,i=mxm; i; --i)//倍增求解
if(fa[s][i]&&disa[s][i]+disb[s][i]+ans.first+ans.second<=x)//能走且距离<=x
ans.first+=disa[s][i],ans.second+=disb[s][i],s=fa[s][i];//更新AB路程
if(fa[s][0]&&ans.first+ans.second+disa[s][0]<=x)ans.first+=disa[s][0];//若A还能走,再走一次
return ans;
}


第一问：

枚举从每个点出发
分别用倍增计算出A,B走的路程
和当前最优值比较，更新答案和当前最优值

void solve_begin()
{
long long ans=0,i;
pair sol,mn;
for(mn.first=1,mn.secOnd=0,i=1; i<=n; ++i)//枚举从每个点出发
{
sol=solve(i,x0);//计算两人路程
if(sol.second&&((sol.first*mn.secOnd==sol.second*mn.first&&h[ans] mn=sol,ans=i;
}
printf("%lld\n",ans);
return;
}


第二问：

输入询问,计算答案,输出答案
用倍增计算出A,B走的路程

void solve_end()
{
long long m,i,x,y;
pair sol;
for(scanf("%lld",&m),i=1; i<=m; ++i)scanf("%lld%lld",&x,&y),sol=solve(x,y),printf("%lld %lld\n",sol.first,sol.second);//输入询问,计算答案,输出答案
return;
}

CODE

//Before nobody understood the code
#include
#include
#include
#include
#include
using namespace std;
const long long mxn=100000,mxm=30,INF=0x7f7f7f7f;
long long n,x0,h[mxn+10],disa[mxn+10][mxm+10],disb[mxn+10][mxm+10],fa[mxn+10][mxm+10],fb[mxn+10],l[mxn+10],r[mxn+10];
struct CITY
{
long long id,h;
} city[mxn+10];
void input()//输入
{
long long i;
for(scanf("%lld",&n),i=1; i<=n; ++i)scanf("%lld",&h[i]),city[i].id=i,city[i].h=h[i];
scanf("%lld",&x0);
return;
}
bool sortcmp(CITY a,CITY b)
{
return a.h}
long long cmp(long long x,long long y,long long dx,long long dy)//两个点找最优,x,y点id,dx,dy到正在找的点的距离
{
if(dx==INF&&dy==INF)return 0;//无解
if(dx==dy)//距离相等
{
if(h[x] return y;
}
if(dx return y;
}
long long cmp_two(long long x)
{
long long disl=INF,disr=INF;
if(l[x])disl=abs(h[l[x]]-h[x]);//计算左右距离
if(r[x])disr=abs(h[r[x]]-h[x]);
return cmp(l[x],r[x],disl,disr);
}
long long cmp_four(long long x)
{
long long ld,rd,lld,rrd,lw,rw,dislw,disrw,w=cmp_two(x);
ld=lld=rd=rrd=dislw=disrw=INF;
if(l[x]&&l[x]!=w)ld=abs(h[x]-h[l[x]]);//不为最小值，计算左右距离
if(r[x]&&r[x]!=w)rd=abs(h[x]-h[r[x]]);
if(l[l[x]])lld=abs(h[l[l[x]]]-h[x]);
if(r[r[x]])rrd=abs(h[r[r[x]]]-h[x]);
lw=cmp(l[l[x]],l[x],lld,ld);//计算左边2个点的最优位置
rw=cmp(r[r[x]],r[x],rrd,rd);//计算右边2个点的最优位置
if(lw)dislw=abs(h[lw]-h[x]);//计算距离
if(rw)disrw=abs(h[rw]-h[x]);
return cmp(lw,rw,dislw,disrw);//计算最优点
}
void work()
{
long long i;
sort(city+1,city+1+n,sortcmp);//排序
for(i=1; i<=n; ++i)l[city[i].id]=city[i-1].id,r[city[i].id]=city[i+1].id;//双向链表
for(i=1; i<=n; ++i)
{
fb[i]=cmp_two(i);//左右找最小
disb[i][0]=abs(h[i]-h[fb[i]]);
fa[i][0]=cmp_four(i);//周围四个找次小
disa[i][0]=abs(h[i]-h[fa[i][0]]);
if(l[i])r[l[i]]=r[i];//删除当前点
if(r[i])l[r[i]]=l[i];//保证一直向东走
}
return;
}
void DP()
{
long long i,j;
for(i=1; i<=n; i++)//预处理AB各走一次的值
{
fa[i][1]=fb[fa[i][0]];//fa[i][j]表示从i走2^j步到达的点(不管AB走)
disa[i][1]=disa[i][0];//disa[i][j]表示从i走2^j步过程中A走的路程
disb[i][1]=disb[fa[i][0]][0];//disb[i][j]表示从i走2^j步过程中B走的路程
}
for(j=2; j<=mxm; ++j)//根据预处理,计算AB走2^j次的值
for(i=1; i<=n; ++i)//倍增
{
fa[i][j]=fa[fa[i][j-1]][j-1];
disa[i][j]=disa[i][j-1]+disa[fa[i][j-1]][j-1];
disb[i][j]=disb[i][j-1]+disb[fa[i][j-1]][j-1];
}
return;
}
pair solve(long long s,long long x)
{
long long i;
pair ans;
for(ans.first=ans.secOnd=0,i=mxm; i; --i)//倍增求解
if(fa[s][i]&&disa[s][i]+disb[s][i]+ans.first+ans.second<=x)//能走且距离<=x
ans.first+=disa[s][i],ans.second+=disb[s][i],s=fa[s][i];//更新AB路程
if(fa[s][0]&&ans.first+ans.second+disa[s][0]<=x)ans.first+=disa[s][0];//若A还能走,再走一次
return ans;
}
void solve_begin()
{
long long ans=0,i;
pair sol,mn;
for(mn.first=1,mn.secOnd=0,i=1; i<=n; ++i)//枚举从每个点出发
{
sol=solve(i,x0);//计算两人路程
if(sol.second&&((sol.first*mn.secOnd==sol.second*mn.first&&h[ans] mn=sol,ans=i;
}
printf("%lld\n",ans);
return;
}
void solve_end()
{
long long m,i,x,y;
pair sol;
for(scanf("%lld",&m),i=1; i<=m; ++i)scanf("%lld%lld",&x,&y),sol=solve(x,y),printf("%lld %lld\n",sol.first,sol.second);//输入询问,计算答案,输出答案
return;
}
int main()
{
input(),work(),DP(),solve_begin(),solve_end();
return 0;
}
//Now,everybody understands the code.