思路与算法

从东向西维护按海拔排序的城市集合，当前高度左右各取最多两个邻居，再按“距离、海拔”排序，得到最近城市B[i]和次近城市A[i]。将小A一步加小B一步作为一个完整轮次，预处理2^k轮后的城市及两人的路程。查询时从大到小选择预算能容纳的轮次，最后尝试补走一段小A。枚举全部起点计算X0下的结果，以整数交叉相乘比较有限比值，同值选海拔高者；B路程0视为无穷。

正确性说明

海拔有序时，每侧超过第二个邻居的城市距离不会优于该侧前两名，所以四个候选足以确定整体前两名。后续行驶完全由当前城市和司机决定，完整轮次总回到小A开车，故可以倍增合并。每段距离非负且海拔互异保证正数，跳过可容纳的最大轮次前缀不会改变路线，预算不够时即应停驶。最后只能剩下小A一段，查询因此准确。穷举所有起点并按题定比值和海拔比较得到最优起点。

复杂度

后缀有序集合初始化及邻居求解O(N log N)，倍增表初始化和构造O(N log N)，每次旅行O(log N)。全起点评选及M次查询总O((N+M)log N)，空间O(N log N)。

易错点

等距按较低海拔优先，但最优起点比值平局按较高海拔优先，两个规则不同。没有次近城市时A不能改走最近。预算由两人共同消耗。B为0包括0/0均是无穷；有限比值不用浮点比较，交叉乘积可用128位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n))
        return 0;
    vector<long long> h(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> h[i];
    vector<int> A(n + 1), B(n + 1);
    set<pair<long long, int>> st;
    for (int i = n; i >= 1; i--) {
        auto it = st.lower_bound({h[i], 0});
        vector<int> cand;
        auto p = it;
        for (int k = 0; k < 2 && p != st.end(); k++, p++)
            cand.push_back(p->second);
        p = it;
        for (int k = 0; k < 2 && p != st.begin(); k++) {
            --p;
            cand.push_back(p->second);
        }
        sort(cand.begin(), cand.end(), [&](int a, int b) {
            long long x = llabs(h[a] - h[i]), y = llabs(h[b] - h[i]);
            return x != y ? x < y : h[a] < h[b];
        });
        if (cand.size())
            B[i] = cand[0];
        if (cand.size() > 1)
            A[i] = cand[1];
        st.insert({h[i], i});
    }
    const int L = 18;
    vector<vector<int>> to(L, vector<int>(n + 1));
    vector<vector<long long>> da(L, vector<long long>(n + 1)), db = da;
    for (int i = 1; i <= n; i++)
        if (A[i] && B[A[i]]) {
            to[0][i] = B[A[i]];
            da[0][i] = llabs(h[i] - h[A[i]]);
            db[0][i] = llabs(h[A[i]] - h[to[0][i]]);
        }
    for (int k = 1; k < L; k++)
        for (int i = 1; i <= n; i++) {
            int j = to[k - 1][i];
            if (j && to[k - 1][j]) {
                to[k][i] = to[k - 1][j];
                da[k][i] = da[k - 1][i] + da[k - 1][j];
                db[k][i] = db[k - 1][i] + db[k - 1][j];
            }
        }
    auto travel = [&](int s, long long budget) {
        long long a = 0, b = 0;
        for (int k = L - 1; k >= 0; k--)
            if (to[k][s] && da[k][s] + db[k][s] <= budget) {
                budget -= da[k][s] + db[k][s];
                a += da[k][s];
                b += db[k][s];
                s = to[k][s];
            }
        if (A[s] && llabs(h[A[s]] - h[s]) <= budget)
            a += llabs(h[A[s]] - h[s]);
        return make_pair(a, b);
    };
    long long X;
    cin >> X;
    int best = 1;
    auto val = travel(1, X);
    for (int i = 2; i <= n; i++) {
        auto v = travel(i, X);
        bool less = v.second && (val.second == 0 ||
                                 (__int128)v.first * val.second < (__int128)val.first * v.second);
        bool equal = (!v.second && !val.second) ||
                     (v.second && val.second &&
                      (__int128)v.first * val.second == (__int128)val.first * v.second);
        if (less || (equal && h[i] > h[best])) {
            best = i;
            val = v;
        }
    }
    cout << best << '\n';
    int m;
    cin >> m;
    while (m--) {
        int s;
        cin >> s >> X;
        auto v = travel(s, X);
        cout << v.first << ' ' << v.second << '\n';
    }
}