一道相当棒的倍增优化DP。
首先我们考虑这样一个问题：对于任意(a_i)，求：
[min|a_i-a_j|(j>i)
]
若有多解，选择编号最小的。
对于这样的问题，我们可以利用平衡树（set）。对于(a_i)而言，它的最小值一定是它的前驱或后继。
我们不妨可以预处理每一位上最近的一位(g_b)即可，从(n)到(1)倒序处理。
接下来是本题的重点：
定义：(f[i,j,0/1])代表从(j)这座城市要走(2^i)天，(0)代表小A先开车，(1)代表小B先开车所能够到达的位置。
(da[i,j,0/1])代表小A走的路程，(db[i,j,0/1])代表小B走的路程；
预处理后，我们开始解决问题了。对于一个问题，从出发点(j)开始，我们可以不断倍增，算出小A和小B各自所走路程。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
const int SIZE = 100000 + 5, INF = 2100000000;
struct city
{
int id, h;
bool operator < (const struct city &lhs) const
{
return h < lhs.h;
}
};
multiset <city> p;
int n, m, t, disa, disb, x[SIZE], s[SIZE], f[40][SIZE][2];
int h[SIZE], da[40][SIZE][2], db[40][SIZE][2];
void calc(int cur, int dis)
{
int op = 0;
disa = disb = 0;
for(int i = t; i >= 0; -- i)
{
if(f[i][cur][op] && disa + disb + da[i][cur][op] + db[i][cur][op] <= dis)
{
disa += da[i][cur][op], disb += db[i][cur][op];
cur = f[i][cur][op];
op = i == 0 ? 1 : 0;
}
}
if(f[0][cur][op] && disa + disb + da[0][cur][op] + db[0][cur][op] <= dis) disa += da[0][cur][op], disb += db[0][cur][op];
return;
}
int main()
{
p.clear();
scanf("%d", &n);
t = log(n) / log(2);
for(int i = 1; i <= n; ++ i) scanf("%d", &h[i]);
scanf("%d", &x[0]);
scanf("%d", &m);
for(int i = 1; i <= m; ++ i) scanf("%d %d", &s[i], &x[i]);
memset(f, 0, sizeof(f));
memset(da, 0, sizeof(da));
memset(db, 0, sizeof(db));
city st;
st.h = INF, st.id = 0;
p.insert(st), p.insert(st);
st.h = -INF, st.id = 0;
p.insert(st), p.insert(st);
int ga, gb, t1, t2;
multiset <city> :: iterator itL, itR;
city now;
for(int j = n; j > 0; -- j)
{
now.h = h[j], now.id = j;
p.insert(now);
itR = p.lower_bound(now);
itL = itR, -- itL, ++ itR;
t1 = (*itL).h, t2 = (*itR).h;
if(abs(h[j] - t1) <= abs(t2 - h[j])) gb = (*itL).id, -- itL;
else gb = (*itR).id, ++ itR;
t1 = (*itL).h, t2 = (*itR).h;
if(abs(h[j] - t1) <= abs(t2 - h[j])) ga = (*itL).id;
else ga = (*itR).id;
f[0][j][0] = ga, f[0][j][1] = gb, da[0][j][0] = abs(h[j] - h[ga]), db[0][j][1] = abs(h[j] - h[gb]);
}
for(int i = 1; i <= t; ++ i)
{
for(int j = 1; j <= n; ++ j)
{
for(int op = 0; op < 2; ++ op)
{
if(i == 1)
{
f[i][j][op] = f[i - 1][f[i - 1][j][op]][1 - op];
da[i][j][op] = da[i - 1][j][op] + da[i - 1][f[i - 1][j][op]][1 - op];
db[i][j][op] = db[i - 1][j][op] + db[i - 1][f[i - 1][j][op]][1 - op];
}
else
{
f[i][j][op] = f[i - 1][f[i - 1][j][op]][op];
da[i][j][op] = da[i - 1][j][op] + da[i - 1][f[i - 1][j][op]][op];
db[i][j][op] = db[i - 1][j][op] + db[i - 1][f[i - 1][j][op]][op];
}
}
}
}
double val = INF;
int ans = h[n - 1] > h[n] ? n - 1 : n;
for(int i = n - 2; i > 0; -- i)
{
calc(i, x[0]);
if(val > (double)disa / disb)
{
val = (double)disa / disb;
ans = i;
}
else if(val == (double)disa / disb && h[i] > h[ans]) ans = i;
}
printf("%d
", ans);
for(int i = 1; i <= m; ++ i)
{
calc(s[i], x[i]);
printf("%d %d
", disa, disb);
}
return 0;
}