倍增

这道题最难的应该是预处理。。。

首先用$set$从后往前预处理出每一个点海拔差绝对值得最大值和次大值

因为当前城市的下标只能变大，对于点$i$，在$set$中二分找出与其值最接近的下标

然后再$set$中将左右各两个下标处理出来，取最大值和次小值

预处理完毕

将每一次小A和小B的开车看为一轮开车

然后用$g[i][j]$表示从第i个点出发经过了$2^{j}$轮开车到达的点

$la[i][j]$表示从第i个点出发经过了$2^{j}$轮开车小A开的路程

$lb[i][j]$表示从第i个点出发经过了$2^{j}$轮开车小B开的路程

然后就是倍增处理

还有要注意，当完整的一轮无法在进行后，小A还有可能再开一轮车，进行判断即可

#include
#define ll long long
#define inf 1e9
using namespace std;
const ll MAXN=100100;
ll n,x0,a[MAXN],b[MAXN],g[MAXN][32];
ll h[MAXN],where,ding,m;
ll la[MAXN][32],lb[MAXN][32];
double MIN;
set > s;
bool cmp(pair a,pair b)
{
return (abs(a.first-ding)=1;i--)//预处理
{
bool bl=0;
set > :: iterator it,be;
vector > k;
k.clear();
it=s.lower_bound(make_pair(h[i],i));
be=s.begin();
be--;
if (it!=s.end())
{
k.push_back(*it);
it++;
bl=1;
}
if (it!=s.end())
k.push_back(*it);
if (bl)
it--;
it--;
if (it!=be)
{
k.push_back(*it);
it--;
}
if (it!=be)
k.push_back(*it);//处理出左右4个点
ding=h[i];
sort(k.begin(),k.end(),cmp);
b[i]=k[0].second;//取最大
a[i]=k[1].second;//取次大
s.insert(make_pair(h[i],i));
}
for (ll i=1;i<=n;i++) { g[i][0]=-1; if (a[i]!=-1 && b[a[i]]!=-1) { la[i][0]=abs(h[i]-h[a[i]]); lb[i][0]=abs(h[a[i]]-h[b[a[i]]]); g[i][0]=b[a[i]];//倍增预处理 } } for (ll i=1;i<=30;i++) { for (ll j=1;j<=n;j++) { if (g[j][i-1]!=-1 && g[g[j][i-1]][i-1]!=-1)//保证不会超出范围 { g[j][i]=g[g[j][i-1]][i-1]; la[j][i]=la[j][i-1]+la[g[j][i-1]][i-1]; lb[j][i]=lb[j][i-1]+lb[g[j][i-1]][i-1];//进行倍增 } else g[j][i]=-1; } } scanf("%lld",&x0); MIN=1.0e18+10; where=0; for (ll i=1;i<=n;i++) { ll ta,tb,now; ta=tb=0; now=i; for (ll j=30;j>=0;j--)//搜索
{
if (g[now][j]!=-1 && ta+tb+la[now][j]+lb[now][j]<=x0) { ta+=la[now][j]; tb+=lb[now][j]; now=g[now][j]; } } if (a[now]!=-1 && ta+tb+abs(h[now]-h[a[now]])<=x0) { ta+=abs(h[now]-h[a[now]]); now=a[now]; } double temp; if (tb==0) temp=1.0e18; else temp=(double)(1.0*ta)/(1.0*tb); if (temph[where])
where=i;
}
}
printf("%lld\n",where);
scanf("%lld",&m);
for (ll i=1;i<=m;i++) { ll now,x; scanf("%lld%lld",&now,&x); ll ta,tb; ta=tb=0; for (ll j=30;j>=0;j--)
{
if (g[now][j]!=-1 && ta+tb+la[now][j]+lb[now][j]<=x)
{
ta+=la[now][j];
tb+=lb[now][j];
now=g[now][j];
}
}
if (a[now]!=-1 && ta+tb+abs(h[now]-h[a[now]])<=x)
{
ta+=abs(h[now]-h[a[now]]);
now=a[now];
}
printf("%lld %lld\n",ta,tb);
}
}