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

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

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

2、对任意给定的 $x=x_i和出发城市s_i$小 \text{A}A 开车行驶的路程总数以及小 \text BB 行驶的路程总数。

输入格式

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

第二行有 n个整数，每两个整数之间用一个空格隔开，依次表示城市 1 到城市 n 的海拔高度，即 $h_1,h_2...h_n$ ，且每个 $h_i$ 都是互不相同的。

第三行包含一个整数 $x_0$

第四行为一个整数 m，表示给定 m 组 $s_i和x_{i}x$

接下来的 m 行，每行包含 2 个整数 $s_i和x_i$ ，表示从城市$s_i$ 出发，最多行驶 $x_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 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\le n\le 20,1\le m\le 20；$
$对于40\%的数据，有1\le n\le 100,1\le m\le 100；$
$对于50\%的数据，有1\le n\le 100,1\le m\le 1000；$
$对于70\%的数据，有1\le n\le 1000,1\le m\le 10^4$
$于100\%的数据：1\le n,m\le 10^5,-10^9\le h_i\le 10^9,1\le s_i\le n,0\le x_i\le 10^9，数据保证h_i互不相同。$

SOLUTION

记得开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]<h[y])return x;//比较海拔return y;}if(dx<dy)return x;//比较距离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<long long,long long> solve(long long s,long long x)
{long long i;pair<long long,long long> 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)//能走且距离<=xans.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<long long,long long> 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]<h[i])||sol.first*mn.second<sol.second*mn.first))//如果小B路程为0,AB比值更优,更新答案mn=sol,ans=i;}printf("%lld\n",ans);return;
}

第二问：

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

void solve_end()
{long long m,i,x,y;pair<long long,long long> 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<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
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<b.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]<h[y])return x;//比较海拔return y;}if(dx<dy)return x;//比较距离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<long long,long long> solve(long long s,long long x)
{long long i;pair<long long,long long> 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)//能走且距离<=xans.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<long long,long long> 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]<h[i])||sol.first*mn.second<sol.second*mn.first))//如果小B路程为0,AB比值更优,更新答案mn=sol,ans=i;}printf("%lld\n",ans);return;
}
void solve_end()
{long long m,i,x,y;pair<long long,long long> 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.