【题目链接】
【题目大意】
从西到东的坐标轴\([1,n]\)上有\(n\)个海拔互不相同的城市，每两个城市之间的距离定义为\(dis(i,j)=|h_i-h_j|\)
小\(A\)和小\(B\)轮着开车，小\(A\)先开始开车。两个人的车一直向东行驶，并且最多行驶\(X\)公里。
小\(A\)和小\(B\)开车的习惯不一样。如果开车从西到东，小\(A\)每一次都会找到后面海拔和当前城市相差次小的城市，小\(B\)则会选择最小值。
如果多个满足条件的城市，那么选择海拔较低的。
现在请回答两个问题：
【思路要点】
【代码】
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define REP(i, s, t) for (int i = s; i <= t; i++)
#define PER(i, s, t) for (int i = s; i >= t; i--)
#define FI first
#define SE second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <class T>
void rd(T& x) {
x = 0; char ch = 0; int f = 1;
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
f = -1;
for (; isdigit(ch); ch = getchar())
x = x * 10 + ch - 48;
x *= f;
}
template<class T>
void pr(T x){
if (!x) {
putchar('0');
return;
}
if (x < 0)
putchar('-'), x = -x;
static int stk[25], top; top=0;
while (x)
stk[++top] = x % 10, x /=10;
while(top)
putchar(stk[top--] + 48);
}
const int N = 1e5 + 5;
const int MG = 27;
const double eps = 1e-7;
int n;
int h[N];
set<pii> st;
int ga[N], gb[N];
int f[MG][N][2], da[MG][N][2], db[MG][N][2];
// f[2 ^ i days][start at j city][first driver is (a = 0, b = 1)] to city
// da[2 ^ i days][start at j city][first driver is (a = 0, b = 1)] distance of a
// db[2 ^ i days][start at j city][first driver is (a = 0, b = 1)] distance of b
int getDis(int i, int j) {
return abs(h[i] - h[j]);
}
bool equal(double x, double y) {
return x - y <= eps;
}
void preWork() {
st.insert(mp(inf, 0)), st.insert(mp(inf, 0));
st.insert(mp(-inf, 0)), st.insert(mp(-inf, 0));
h[0] = inf;
for (int i = n; i >= 1; i--) {
st.insert(mp(h[i], i));
set<pii>::iterator it, it1, it2, it3, it4;
it = st.find(mp(h[i], i));
++it; it1 = it; ++it; it2 = it;
it = st.find(mp(h[i], i));
--it; it3 = it; --it; it4 = it;
if (getDis((*it1).SE, i) < getDis((*it3).SE, i)) {
gb[i] = (*it1).SE;
if (getDis((*it2).SE, i) < getDis((*it3).SE, i))
ga[i] = (*it2).SE;
else
ga[i] = (*it3).SE;
} else {
gb[i] = (*it3).SE;
if (getDis((*it1).SE, i) < getDis((*it4).SE, i))
ga[i] = (*it1).SE;
else
ga[i] = (*it4).SE;
}
}
for (int i = 1; i <= n; i++) {
f[0][i][0] = ga[i], f[0][i][1] = gb[i];
da[0][i][0] = getDis(i, ga[i]), da[0][i][1] = 0;
db[0][i][0] = 0, db[0][i][1] = getDis(i, gb[i]);
}
for (int j = 1; j <= n; j++)
for (int k = 0; k <= 1; k++) {
f[1][j][k] = f[0][f[0][j][k]][k ^ 1];
da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][k ^ 1];
db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][k ^ 1];
}
for (int i = 2; i <= 24; i++)
for (int j = 1; j <= n; j++)
for (int k = 0; k <= 1; k++) {
f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];
db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
}
}
pii calc(int u, int x) {
pii res = {0, 0};
for (int i = 24; i >= 0; i--)
if (f[i][u][0] && res.FI + res.SE + da[i][u][0] + db[i][u][0] <= x)
res.FI += da[i][u][0], res.SE += db[i][u][0], u = f[i][u][0];
return res;
}
void solve1() {
int x0; rd(x0);
pair<pii, int> res = mp(calc(1, x0), 1);
for (int i = 2; i <= n; i++) {
pii tmp = calc(i, x0);
if (tmp.SE == 0)
continue;
else if ((res.FI.SE == 0) || (1.0 * tmp.FI / tmp.SE < 1.0 * res.FI.FI / res.FI.SE) || (equal(1.0 * tmp.FI / tmp.SE, 1.0 * res.FI.FI / res.FI.SE) && (h[res.FI.SE] < h[tmp.SE])))
res = mp(tmp, i);
}
pr(res.SE), puts("");
}
void solve2() {
int m; rd(m);
while (m--) {
int s0, x0; rd(s0), rd(x0);
pii tmp = calc(s0, x0);
pr(tmp.FI), putchar(' '), pr(tmp.SE), puts("");
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
rd(n);
for (int i = 1; i <= n; i++)
rd(h[i]);
preWork();
solve1(), solve2();
return 0;
}