题解 P1081 【开车旅行】
倍增优化DP：开车旅行
复杂度：O(（N+M）logN)
关键信息：
1.所在城市。
2.已行驶的天数（倍增）。
3.A，B各行驶的路程长度。预处理：（set实现）
nexta：小A沿当前方向到达的下一个城市（即i+1--N中使dist（i，j）取到最小值的城市）。
nextb：小B沿当前方向到达的下一个城市（即i+1--N中使dist（i，j）取到次小值的城市）。
具体实现：由东向西依次将高度插入平衡树。
不妨设：
a=当前点的a前驱 。b=当前点的后继 。c=当前点的前驱的前驱。d=当前点的后继的后继 。
小A要去的城市就是min(a,b,c,d);
小A要去的城市就是a,b,c,d中的次小值;f[i,j,k]：从城市j出发，两人共行驶2的i次方天，k先开车，最终会到达的城市。
详细：
1.k=0，小A先开车。
2.k=1，小B先开车。
3.f[0,j,0]=nexta(j),f[0,j,1]=nextb(j);
4.i==1: f[1,j,k]=f[0,f[0,j,k],1-k];
5.i>1: f[i,j,k]=f[i-1,f[i-1,j,k],k];
Ps：注意超出边界情况。定义：
disa[i,j,k]：从城市j出发，两人共行驶2的i次方，k先开车，小A行驶的路程总长度。
disb[i,j,k]：从城市j出发，两人共行驶2的i次方，k先开车，小B行驶的路程总长度。
初始值：
disa[0,j,0]=dist(j,nexta(j)),disa[0,j,1]=0;
disa[0,j,1]=dist(j,nextb(j)),disb[0,j,1]=0;;
i==1:
disa[1,j,k]=disa[0,j,k]+disa[0,f[0,j,k],1-k];
disb[1,j,k]=disb[0,j,k]+disb[0,f[0,j,k],1-k];
i>1:
disa[i,j,k]=disa[i-1,j,k]+disa[i-1,f[i-1,j,k],k];
disb[i,j,k]=disb[i-1,j,k]+disb[i-1,f[i-1,j,k],k];Calc（S，X）：从城市S出发最多行驶X公里时，A，B各行驶的路程长度。
1.初始化当前城市p=S。A，B累计行驶路程sa=0，sb=0。
2.倒序循环i=logN--0.
3.对于每个i，若两人从p出发行驶2的i次方天，累积路程仍未超过X，即sa+sb+disa[i,p,0]+disb[i,p,0]<=X,则令sa=sa+disa[i,p,0],sb=sb+disb[i,p,0],p=f[i,p,0]。
4.循环结束，答案即为sa和sb。
问题1：枚举起点Si，取A，B行驶路程比值最小的Calc(Si,X0)。
问题2：多次询问Calc(Si,Xi),也可以直接计算。//-------------------------------------------------------------------------------------------
标程时间：
#include<bits/stdc++.h>
#define re register
#define A 100005
#define INF 1234567890000
using namespace std;
int n,x0,T;
int nexta,nextb;
int sa,sb;
int high[A];
int disa[A][20][3],disb[A][20][3],f[A][20][3];
struct Set
{
int id,data;
friend bool operator<(Set a,Set b)
{return a.data<b.data;}
};
multiset<Set>q;
inline int read()
{
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1,ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*f;
}
inline void write(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void Calc(int S,int &a,int &b,int x)//a为sa，b为sb。
{
int now=S;
for(int i=18;~i;--i)
{
if(f[now][i][0]&&a+b+disa[now][i][0]+disb[now][i][0]<=x)
{
a+=disa[now][i][0];
b+=disb[now][i][0];
now=f[now][i][0];
}
}
if(f[now][0][0]&&disa[now][0][0]+a+b<=x)a+=disa[now][0][0];
}
int main()
{
Set a,Aa;
n=read();
for(re int i=1;i<=n;++i)high[i]=read();
high[0]=2e9;high[n+1]=-2e9;
a.id=0;a.data=2e9;q.insert(a);a.data=2e9-1;q.insert(a);
a.id=n+1;a.data=-2e9;q.insert(a);a.data=-2e9+1;q.insert(a);
for(re int i=n;i>0;--i)//预处理
{
Aa.id=i;Aa.data=high[i];
q.insert(Aa);
multiset<Set>::iterator it=q.lower_bound(Aa);
int q1,qd,h1,hd;
++it;h1=(*it).id;hd=(*it).data;
--it;--it;q1=(*it).id;qd=(*it).data;
++it;
if(abs(hd-high[i])>=abs(qd-high[i]))//求前驱后继
{
nextb=q1;
--it;--it;
if(abs(hd-high[i])>abs((*it).data-high[i]))nexta=(*it).id;
else nexta=h1;
}
else
{
nextb=h1;
++it;++it;
if(abs(qd-high[i])>abs((*it).data-high[i]))nexta=(*it).id;
else nexta=q1;
}
//cout<<"nexta: "<<nexta<<" nextb: "<<nextb<<endl;
f[i][0][0]=nexta;f[i][0][1]=nextb;
disa[i][0][0]=abs(high[i]-high[nexta]);disa[i][1][0]=disa[i][0][0];
disb[i][0][1]=abs(high[i]-high[nextb]);disb[i][1][1]=disb[i][0][1];
}
for(re int i=1;i<=n;i++)//处理[...,i(==1),...] 的情况
{
f[i][1][0]=f[f[i][0][0]][0][1];
disa[i][1][0]=disa[i][0][0];
disb[i][1][0]=abs(high[f[i][1][0]]-high[f[i][0][0]]);
f[i][1][1]=f[f[i][0][1]][0][0];
disb[i][1][1]=disb[i][0][1];
disa[i][1][1]=abs(high[f[i][1][1]]-high[f[i][0][1]]);
}
for(re int k=2;k<=18;k++)//动态规划 (i>1)
for(re int i=1;i<=n;i++)
{
f[i][k][1]=f[f[i][k-1][1]][k-1][1];
disb[i][k][1]=disb[f[i][k-1][1]][k-1][1]+disb[i][k-1][1];
disa[i][k][1]=disa[i][k-1][1]+disa[f[i][k-1][1]][k-1][1];
f[i][k][0]=f[f[i][k-1][0]][k-1][0];
disa[i][k][0]=disa[i][k-1][0]+disa[f[i][k-1][0]][k-1][0];
disb[i][k][0]=disb[i][k-1][0]+disb[f[i][k-1][0]][k-1][0];
}
x0=read();T=read();
double ans=INF*10.0;
int id;
for(re int i=1;i<=n;++i)
{
int sa=0,sb=0;
Calc(i,sa,sb,x0);
if(!sb)
{
if(ans>INF)
{
ans=INF;
id=i;
}
else if(ans==INF&&high[id]<high[i])id=i;
}
else
{
double now=(double)sa/(double)sb;
if(now<ans)
{
ans=now;
id=i;
}
else if(now==ans&&high[id]<high[i])id=i;
}
}
write(id);
putchar('\n');
while(T--)
{
int a,b;
int sa=0,sb=0;
a=read();b=read();
Calc(a,sa,sb,b);
write(sa);putchar(' ');write(sb);putchar('\n');
}
return 0;
}