题解 P1081 【开车旅行】

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

旅行过程中，小 $ext{A}$ 和小 $ext{B}$ 轮流开车，第一天小 $ext{A}$ 开车，之后每天轮换一次。他们计划选择一个城市 $s$ 作为起点，一直向东行驶，并且最多行驶 $x$ 公里就结束旅行。

小 $ext{A}$ 和小 $ext{B}$ 的驾驶风格不同，小 $ext{B}$ 总是沿着前进方向选择一个最近的城市作为目的地，而小 $ext{A}$ 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $x$ 公里，他们就会结束旅行。

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

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

对任意给定的 $x=x_i$ 和出发城市 $s_i$ ，小 $ext{A}$ 开车行驶的路程总数以及小 $ext B$ 行驶
的路程总数。

假设这个并非是必须向东行驶。

我们可以对 $h$ 数组进行排序。

则排好序的第 $x$ 个城市，第 $1$ 近的城市和第 $2$ 进的城市，一定在 $x-2,x-1,x+1,x+2$ 这些城市当中。

那么向东行驶怎么处理呢？

我们可以用这样一个思想：

首先，想让第 $x$ 个城市没有向东行的限制，可以直接把 $1 sim x-1$ 这 $x-1$ 个城市删掉。

这样就可以解除向东行的限制。

我们可以试着用一个链表，来模拟这个东西。

priority_queue<pair<int,pair<int,int> > >q;
read(n);
for(int i=1;i<=n;i++){
	read(m[i].h);
	m[i].id=i;
}sort(m+1,m+n+1,cmp);
for(int i=1;i<=n;i++){
	id[m[i].id]=i;
	pre[i]=i-1;lat[i]=i+1;
}
for(int i=1;i<=n;i++){
	while(q.size())q.pop();
	int x=id[i];
	int p1=pre[x],p2=pre[pre[x]],l1=lat[x],l2=lat[lat[x]];
	bool pb1=true,pb2=true,lb1=true,lb2=true;
	if(p1<=0)pb1=false;
	else if(p2<=0)pb2=false;
	if(l1>n)lb1=false;
	else if(l2>n)lb2=false;
	if(pb1){
		q.push(make_pair(-abs(m[x].h-m[p1].h),make_pair(-m[p1].h,p1)));
		if(pb2)q.push(make_pair(-abs(m[x].h-m[p2].h),make_pair(-m[p2].h,p2)));
	}
	if(lb1){
		q.push(make_pair(-abs(m[x].h-m[l1].h),make_pair(-m[l1].h,l1)));
		if(lb2)q.push(make_pair(-abs(m[x].h-m[l2].h),make_pair(-m[l2].h,l2)));
	}
	if(q.size())fi[i]=m[q.top().second.second].id;
	if(q.size())q.pop();
	if(q.size())se[i]=m[q.top().second.second].id;
	lat[p1]=lat[x];pre[l1]=pre[x];
}

我这里是用一个堆， $push$ 了 $leq 4$ 个可能的数，然后搞。

之后就直接倍增，这里就不详细讲了

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &FF){
	T RR=1;FF=0;char CH=getchar();
	for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
	for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
	FF*=RR;
}
const int MAXN=1e5+10;
struct node{
	int h,id;
}m[MAXN];
int n,id[MAXN],pre[MAXN],lat[MAXN],fi[MAXN],se[MAXN],f[MAXN][25],a[MAXN][25],b[MAXN][25],A,B;
double Min=10000000000;
priority_queue<pair<int,pair<int,int> > >q;
bool cmp(node a,node b){
	return a.h<b.h;
}
void work(int x,int x1){
	A=0;B=0;
	for(int j=19;j>=0;j--)
		if(f[x1][j]&&(A+B+a[x1][j]+b[x1][j])<=x){
			A+=a[x1][j];
			B+=b[x1][j];
			x1=f[x1][j];
		}
	if(se[x1]&&A+B+a[x1][0]<=x)A+=a[x1][0];
}
int main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(m[i].h);
		m[i].id=i;
	}sort(m+1,m+n+1,cmp);
	for(int i=1;i<=n;i++){
		id[m[i].id]=i;
		pre[i]=i-1;lat[i]=i+1;
	}
	for(int i=1;i<=n;i++){
		while(q.size())q.pop();
		int x=id[i];
		int p1=pre[x],p2=pre[pre[x]],l1=lat[x],l2=lat[lat[x]];
		bool pb1=true,pb2=true,lb1=true,lb2=true;
		if(p1<=0)pb1=false;
		else if(p2<=0)pb2=false;
		if(l1>n)lb1=false;
		else if(l2>n)lb2=false;
		if(pb1){
			q.push(make_pair(-abs(m[x].h-m[p1].h),make_pair(-m[p1].h,p1)));
			if(pb2)q.push(make_pair(-abs(m[x].h-m[p2].h),make_pair(-m[p2].h,p2)));
		}
		if(lb1){
			q.push(make_pair(-abs(m[x].h-m[l1].h),make_pair(-m[l1].h,l1)));
			if(lb2)q.push(make_pair(-abs(m[x].h-m[l2].h),make_pair(-m[l2].h,l2)));
		}
		if(q.size())fi[i]=m[q.top().second.second].id;
		if(q.size())q.pop();
		if(q.size())se[i]=m[q.top().second.second].id;
		lat[p1]=lat[x];pre[l1]=pre[x];
	}
	for(int i=1;i<=n;i++){
		f[i][0]=fi[se[i]];
		a[i][0]=abs(m[id[i]].h-m[id[se[i]]].h);
		b[i][0]=abs(m[id[fi[se[i]]]].h-m[id[se[i]]].h);
	}
	for(int j=1;j<=20;j++)
		for(int i=1;i<=n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
			a[i][j]=a[i][j-1]+a[f[i][j-1]][j-1];
			b[i][j]=b[i][j-1]+b[f[i][j-1]][j-1];
		}
	int x,ans;read(x);
	for(int i=1;i<=n;i++){
		work(x,i);
		if(B&&1.0*A/B<Min){
			Min=1.0*A/B;
			ans=i;
		}
	}cout<<ans<<endl;
	int T;for(read(T);T--;){
		int j,x;read(j);read(x);
		work(x,j);
		printf("%d %d
",A,B);
	}
	return 0;
}