小 A 和小 B 决定利用假期外出旅行，他们将想去的城市从 到 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 的海拔高度为 ，城市 和城市 之间的距离 恰好是这两个城市海拔高度之差的绝对值，即 。
旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 作为起点，一直向东行驶，并且最多行驶 公里就结束旅行。小 A 和小 B 的驾驶风格不同，小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 公里，他们就会结束旅行。
在启程之前，小 A 想知道两个问题：
- 对于一个给定的 ，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 ，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
- 对任意给定的 和出发城市 ，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。
链接
题解
使用排序 + 链表求出在以个点为起点时，小 A 和小 B 开车到达的地点。
设 表示以小 A（）或小 B（）开始，以 为起点， 天后到达的地点； 表示以小 A（）或小 B（）开始，以 为起点， 天内，小 A（）或小 B（）或二者之和 的路程。
对于第一问，枚举起点即可。
代码
#include <cstdio>
#include <algorithm>
#include <vector>
#include <list>
const int MAXN = 100000;
const int MAXN_LOG = 17; // Math.log2(100000) = 16.609640474436812
const int MAXM = 10000;
struct Node {
long long x;
Node *nextA, *nextB;
std::list<Node *>::iterator it;
} N[MAXN + 1];
int n, logn, f[2][MAXN + 1][MAXN_LOG + 1];
long long g[2][MAXN + 1][MAXN_LOG + 1][3];
inline bool compareNode(Node *a, Node *b) {
return a->x < b->x;
}
inline bool comparePair(const std::pair<long long, Node *> &a, const std::pair<long long, Node *> &b) {
if (a.first == b.first) return a.second->x < b.second->x;
else return a.first < b.first;
}
inline void prepare() {
std::list<Node *> list;
for (int i = 1; i <= n; i++) {
list.push_back(&N[i]);
N[i].it = --list.end();
}
list.sort(&compareNode);
for (int i = 1; i <= n; i++) {
std::vector< std::pair<long long, Node *> > vec;
std::list<Node *>::iterator near;
near = N[i].it, near++;
if (near != list.end()) {
vec.push_back(std::make_pair(abs((*near)->x - N[i].x), *near));
if (++near != list.end()) {
vec.push_back(std::make_pair(llabs((*near)->x - N[i].x), *near));
}
}
near = N[i].it;
if (near != list.begin()) {
near--;
vec.push_back(std::make_pair(abs((*near)->x - N[i].x), *near));
if (near != list.begin()) {
near--;
vec.push_back(std::make_pair(llabs((*near)->x - N[i].x), *near));
}
}
std::sort(vec.begin(), vec.end(), comparePair);
if (vec.size() >= 2) {
N[i].nextA = vec[1].second;
#ifdef DBG
printf("nextA(%lld) = %lld\n", N[i].x, N[i].nextA->x);
#endif
} else N[i].nextA = &N[0];
if (vec.size() >= 1) {
N[i].nextB = vec[0].second;
#ifdef DBG
printf("nextB(%lld) = %lld\n", N[i].x, N[i].nextB->x);
#endif
} else N[i].nextB = &N[0];
list.erase(N[i].it);
}
N[0].nextA = N[0].nextB = &N[0];
// Build graph
for (int i = 1; i <= n; i++) {
f[0][i][0] = N[i].nextA - N;
f[0][i][1] = N[i].nextA->nextB - N;
f[1][i][0] = N[i].nextB - N;
f[1][i][1] = N[i].nextB->nextA - N;
g[0][i][0][0] = g[0][i][0][2] = N[i].nextA == &N[0] ? 0 : llabs(N[i].x - N[i].nextA->x);
g[0][i][0][1] = 0;
g[1][i][0][1] = g[1][i][0][2] = N[i].nextB == &N[0] ? 0 : llabs(N[i].x - N[i].nextB->x);
g[1][i][0][0] = 0;
}
for (int i = 1; i <= n; i++) {
g[0][i][1][0] = g[0][i][0][0];
g[0][i][1][1] = g[1][N[i].nextA - N][0][1];
g[0][i][1][2] = g[0][i][0][0] + g[1][N[i].nextA - N][0][1];
g[1][i][1][1] = g[1][i][0][1];
g[1][i][1][0] = g[0][N[i].nextB - N][0][0];
g[1][i][1][2] = g[1][i][0][1] + g[0][N[i].nextB - N][0][0];
}
while ((1 << logn) <= n) logn++;
logn--;
for (int j = 2; j <= logn; j++) {
for (int i = 1; i <= n; i++) {
for (int k = 0; k < 2; k++) {
for (int l = 0; l < 3; l++) {
g[k][i][j][l] = g[k][i][j - 1][l] + g[k][f[k][i][j - 1]][j - 1][l];
}
f[k][i][j] = f[k][f[k][i][j - 1]][j - 1];
}
}
}
#ifdef DBG
for (int j = 0; j <= logn; j++) {
for (int i = 1; i <= n; i++) {
for (int k = 0; k < 2; k++) {
printf("f(%d, %d, %d) = %d [%lld]\n\n", k, i, j, f[k][i][j], N[f[k][i][j]].x);
for (int l = 0; l < 3; l++) {
printf("g(%d, %d, %d, %d) = %lld\n", k, i, j, l, g[k][i][j][l]);
}
putchar('\n');
}
}
}
#endif
}
inline long long solve(int start, long long limit, long long &sumA, long long &sumB) {
int curr = start;
long long sum = sumA = sumB = 0;
for (int i = logn; i >= 1 && curr != 0; i--) {
while (curr && limit >= sum + g[0][curr][i][2]) {
sum += g[0][curr][i][2];
sumA += g[0][curr][i][0];
sumB += g[0][curr][i][1];
curr = f[0][curr][i];
}
}
if (curr && limit >= sum + g[0][curr][0][0]) {
sumA += g[0][curr][0][0];
sum += g[0][curr][0][0];
}
return sum;
}
inline int solve(long long limit) {
int ans = 0;
double k = -1;
for (int i = 1; i <= n; i++) {
long long tmpA, tmpB;
solve(i, limit, tmpA, tmpB);
double t = static_cast<double>(tmpA) / static_cast<double>(tmpB);
if (k == -1 || t < k || (t == k && N[i].x > N[ans].x)) {
k = t;
ans = i;
}
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &N[i].x);
prepare();
long long limit;
scanf("%lld", &limit);
printf("%d\n", solve(limit));
int m;
scanf("%d", &m);
while (m--) {
int start;
long long limit;
scanf("%d %lld", &start, &limit);
long long sumA, sumB;
solve(start, limit, sumA, sumB);
printf("%lld %lld\n", sumA, sumB);
}
return 0;
}