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和xix
接下来的 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互不相同。
SOLUTION
记得开long longYBT高效进阶，这是我最后做的一题，这题我做了整整半天多
两点间找最优点
先比较距离
若距离都为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出发走2j步的目的点(不论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)//能走且距离<=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<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)//能走且距离<=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<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.