题解：P1081 [NOIP2012 提高组] 开车旅行
违规用户名1017748 · · 题解
Part 1 预处理 首先要处理出小A和小B怎么走。 我们用ga（i）、gb（i)分别表示小A、小B行驶到的下一个城市 容易想到，嗯，
法一：暴力求解 枚举1-n的每一个城市，对于每个城市i，从（i+1-n）中选取距离最小的两个城市。时间复杂度 n^2.爆啦！surprise mother f**k
接下来讲讲正解，有个神奇的东西叫做#inclue<set>
它支持logn级别的插入和查询，并对内部的数进行排序
s.insert(x);//插入x s.lower_bound(x);//查找大于等于x的最小元素，返回迭代器 s.upper_bound(x);//查找大于x的最小元素，返回迭代器 所以。对于当前城市i
最近的和第二近的只会在
四个位置出现 PS：这里有个细节，他们只能向编号更大的城市走去，所以可以用个小技巧，倒着处理**。
for(int i=n; i>=1; i--) q.insert(h[i]); Part 2 动态规划
- 本题关键 在哪里（城市） 开了多久（天数） A、B行驶的长度 但其实知道前两个就可以推出第三个。
因此我们可以定义
f[i,j,k]表示从城市j出发，两人一共行驶i天，k先开车最终会到达的城市。其中k=0表示A开车，k=1表示B开车。 于是终极大魔王出现了！
倍增DP 我们将i改为一共行驶了2^i天。
于是初值：
f[0,j,0]=ga(j),f[0,j,1]=gb(j) 当i=1时，因为2^0是奇数，所以两人从j出发开2^1天所到达的城市，等于k先开2^0天，另一人再开2^0天所到达的城市
f[1,j,k]=f[0,f[0,j,k]，1-k/换了个人开/] 当i>1时，你怎么折腾2^i都是偶数，所以不会换人，而两人从j出发开2^i天所到达的城市，等于等于k先开2^i-1天，k再开2^i-1天所到达的城市。
所以
f[i,j,k]=f[i-1,f[i-1,j,k],k] **这里有个小问题，需要注意超出n的边界的情况，所以需要特判 鉴于f数组，于是易得
定义da[i,j,k]表示从j城出发，由k先开，行驶2^i天，小A走的路程
当i==1时da[1,j,k]=da[0,j,k]+da[0,f[0,j,k],i-k];
否则 da[i,j,k]=da[i-1,j,k]+da[i-1,f[0,j,k],1-k];
我们定义db[i,j,k]表示从j城出发，由k先开，行驶2^i天,小B走的路程
当i==1时db[1,j,k]=db[0,j,k]+db[0,f[0,j,k],i-k];
否则 db[i,j,k]=db[i-1,j,k]+db[i-1,f[0,j,k],1-k];
时间复杂度Nlog N. 但是这里仅算出了2^i次方下的情况。于是我们需要满足求出从城市S出发最多行驶X公里时，A和B走了多远。
我们按倒叙枚举2的i次方，基于二进制划分的思想来拼凑X。
1.倒叙循环i=logN-0
2.对于每个i若两人从p出发行驶2^i天累计路程仍未超过x，则令累计路程加上x，并行驶到该城市
3.循环结束后即为所求。
最终实现了logN查询的复杂度。
然后对于问题。。。
[问题1]枚举！然后计算取比值最小的即为答案 [问题2]多次计算。
于是整个算法的时间复杂度O((N+M)log N)
代码来了:
#include<iostream>
#include<set>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
//最大坑点！本题要开long long
const long long INF=0x7fffffffffffffff/2;
double ans=10000000000;
struct node
{
long long h;
int id;
} h[100005],ga[100005],gb[100005];//储存城市信息
struct point
{
long long la,lb;
};
bool operator <(node as,node bs)
{
if(as.h!=bs.h)return as.h<bs.h;
else return as.id<bs.id;
}//重载运算符
set<node> q;//以城市为单位入set
int n,f[20][100005][3];
long long da[20][100005][3],db[20][100005][3];
bool cmp(node as,node bs)
{
return as.h<bs.h;
}
point Calc(int p,int x)//计算以p为起点，行驶距离不超过x的路程和
{
long long la=0,lb=0;
for(int i=18; i>=0; i--)//倒叙
{
if(f[i][p][0]&&la+lb+da[i][p][0]+db[i][p][0]<=x)
{
la+=da[i][p][0];
lb+=db[i][p][0];
p=f[i][p][0];
}
}
return {la,lb};
}
int main()
{
scanf("%d",&n);
q.insert({INF,0});
q.insert({INF-1,0});
q.insert({-INF,0});
q.insert({-INF+1,0});//边界处理，预防预处理时越界
for(int i=1; i<=n; i++)
{
scanf("%lld",&h[i].h);
h[i].id=i;
}
for(int i=n; i>=1; i--)//倒叙
{
q.insert(h[i]);
node t[5];
t[1]=*--q.lower_bound(h[i]);
t[2]=*--q.lower_bound(t[1]);
t[3]=*q.upper_bound(h[i]);
t[4]=*q.upper_bound(t[3]);//查找4个可能为最近城市
for(int j=1; j<=4; j++)t[j].h=abs(t[j].h-h[i].h);
sort(t+1,t+5,cmp);//排序
ga[i]=t[2];
gb[i]=t[1];
}
for(int i=1; i<n; i++)
{
f[0][i][0]=ga[i].id;
f[0][i][1]=gb[i].id;
}
for(int i=1; i<=18; i++)
for(int j=1; j<=n; j++)
if(j+(1<<i)<=n)//预防越界
for(int k=0; k<=1; k++)
{
if(i==1)f[1][j][k]=f[0][f[0][j][k]][1-k];
else f[i][j][k]=f[i-1][f[i-1][j][k]][k];
}
memset(da,127/3,sizeof(da));
memset(db,127/3,sizeof(db));//当不可到达时默认为最大
for(int i=1; i<=n; i++)
{
da[0][i][0]=ga[i].h;
da[0][i][1]=0;
}
for(int i=1; i<=18; i++)
for(int j=1; j<=n; j++)
if(j+(1<<i)<=n)//预防越界
for(int k=0; k<=1; k++)
{
if(i==1)
{
da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];
}
else da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
}
for(int i=1; i<=n; i++)
{
db[0][i][0]=0;
db[0][i][1]=gb[i].h;
}
for(int i=1; i<=18; i++)
for(int j=1; j<=n; j++)
if(j+(1<<i)<=n)//预防越界
for(int k=0; k<=1; k++)
{
if(i==1)
{
db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][k^1];
}
else db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
}
int x0,m;
scanf("%d",&x0);
int ddd=0;
for(int i=1; i<=n; i++)//枚举找出最小比
{
point tmp=Calc(i,x0);
if(tmp.lb==0)continue;//防止除0
double ccf=(long double)tmp.la/(long double)tmp.lb;
if(ccf<ans)ans=ccf,ddd=i;
}
printf("%d\n",ddd);
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
int si,xi;
scanf("%d%d",&si,&xi);
point tmp=Calc(si,xi);//依次计算
printf("%lld %lld\n",tmp.la,tmp.lb);
}
}