开车旅行

GitHub跳转原题关系图返回列表

海拔排序双向链表 O(N) 求出每座城市东侧的最近与次近城市，再用倍增预处理「走 2^k 步后到哪、两人各开多少公里」，每个询问 O(log N) 跳跃回答。

OJ: roj

题目 ID: 3154

难度:提高+/省选-

标签:倍增链表预处理python

创建: 2026-10-01 21:19

更新: 2026-10-10 11:30

形式化题目

数轴上有 $N$ 座城市，编号 $1 \ldots N$ 自西向东排列，海拔 $H_1 \ldots H_N$ 互不相同。城市 $i, j$ 之间的距离为 $d[i,j] = |H_i - H_j|$ 。

从某座城市 $S$ 出发只能向东（编号增大方向）前进。行进规则：

当前司机为小A 时，走到东侧第二近的城市；当前司机为小B 时，走到东侧最近的城市；
两个候选城市距离相同时，海拔低者视为更近；
第一天由小A 先开车，之后每天轮换；
若某位司机在当前位置以东找不到自己的目标城市，或者开过去会使累计里程超过 $X$ ，旅行立即结束。

需要回答两个问题：

给定 $X_0$ ：从哪个城市出发，小A 的总里程与小B 的总里程之比最小？小B 里程为 $0$ 时比值视为 $+\infty$ ，两个 $+\infty$ 相等；比值并列时取出发城市海拔最高者，输出该城市编号。
给定 $M$ 组 $(S_i, X_i)$ ：输出小A、小B 各自的总里程。

flowchart LR
    C1["1 · H=4"] --- C2["2 · H=5"] --- C3["3 · H=6"] --- C4["4 · H=1"] --- C5["5 · H=2"] --- C6["6 · H=3"] --- C7["7 · H=7"] --- C8["8 · H=8"] --- C9["9 · H=9"] --- C10["10 · H=10"]
    C1 -- "A +1" --> C2
    C2 -- "B +1" --> C3
    C3 -- "A +2" --> C8
    C8 -- "B +1" --> C9
    C9 -. "小A 找不到次近，停" .-> C10

上图画出样例中 $S=1,\ X=7$ 的完整旅程：小A 先从 $1$ 开到第二近的 $2$ （+1），小B 从 $2$ 开到最近的 $3$ （+1），小A 从 $3$ 开到第二近的 $8$ （+2），小B 从 $8$ 开到 $9$ （+1）。累计 $5$ 公里后轮到小A，但 $9$ 以东只剩城市 $10$ ，小A 找不到「第二近」的城市，旅行结束。四段依次由 A、B、A、B 先开，单段里程记在先开者名下，故小A 合计 $1+2=3$ 、小B 合计 $1+1=2$ ，正是样例第一行询问 $S=1$ 的输出 3 2。

正解

思路

第一步：O(N) 找出每个城市东侧的「最近」与「次近」。

如果把所有城市按海拔排成一条双向链表，那么城市 $i$ 的最近、次近城市只会出现在链表上它左右各 2 个邻居里：设 $j$ 与 $i$ 之间隔着城市 $t$ （海拔介于两者之间），则

d[i,j] = d[i,t] + d[t,j] > d[i,t],

即隔着城市的 $j$ 永远不如中间的 $t$ 近。所以每个城市只需考察至多 4 个候选。

但题目要求目的地在东侧（编号更大）。技巧是按编号 $1 \ldots N$ 的顺序处理城市，处理完 $i$ 就把它从链表里删掉——这样轮到 $i$ 时，链表里剩下的恰好只有 $i$ 自己和东侧城市，4 个邻居全部合法。把候选按（距离，海拔）排序：第 1 名给小B，第 2 名给小A。排序是唯一的大开销，总计 $O(N \log N)$ 。

第二步：把「路径完全确定」变成倍增。

起点定了，谁先开定了，之后的路径就唯一确定；每天的状态只有「当前城市 + 当前司机」。逐日模拟一次是 $O(N)$ ， $M$ 次询问加枚举起点共 $O(NM) \approx 10^9$ ，不可接受。于是对「走 $2^k$ 步」建表：

nxt[k][w][i]：从 $i$ 出发、由 $w$ （0 = 小A，1 = 小B）先开，走 $2^k$ 步后到达的城市（ $0$ 表示走不动）；
da[k][w][i]、db[k][w][i]：这 $2^k$ 步里两人各自的里程。

拼接 $2^k = 2^{k-1} + 2^{k-1}$ 时，后一段的先开者 $w_2$ 只跟 $k$ 有关：

flowchart LR
    subgraph K1["k = 1：共 2 步"]
        s1["i, w"] -->|"1 步，换人"| m1["mid, w^1"] -->|"1 步，再换人"| e1["2^k 后，回到 w"]
    end
    subgraph K2["k ≥ 2：两段各 2^(k-1) ≥ 2 步（偶数）"]
        s2["i, w"] -->|"2^(k-1) 步"| m2["mid, w"] -->|"2^(k-1) 步"| e2["2^k 后，仍是 w"]
    end

$k = 1$ ：整段 2 步 = 1 步 + 1 步，中途换人， $w_2 = w \oplus 1$ ；
$k \geqslant 2$ ：前后两段各有偶数步，先开者换回去， $w_2 = w$ 。

边界 $k=0$ 是单步：从 $i$ 开到它的目标城市，这一步里程记在先开者名下，走完换司机。三层递推：

\text{nxt}[k][w][i] = \text{nxt}[k{-}1][w_2]\big[\text{nxt}[k{-}1][w][i]\big],

里程数组把两段的 da、db 分别相加即可。中途任一段走不动（ $0$ ）整段记 $0$ 。

第三步：跳跃回答。 从高位到低位枚举 $k$ ：若 nxt[k][w][cur] 存在且跳过去累计里程不超 $X$ ，就跳，累加两人里程； $k=0$ 的跳跃成功后翻转司机。任何可行步数 $s \leqslant N-1 < 2^{\log}$ 都能二进制分解，从高到低位试跳恰好逐位重建整条路径，单次询问 $O(\log N)$ 。

第四步：两个问题的回答。 问题 2 直接 drive(S_i, X_i)。问题 1 枚举所有起点调用同一函数得 $(a, b)$ ，比较 $\frac{a}{b}$ 用交叉相乘 $a \cdot b' \text{ vs } a' \cdot b$ （全程整数，无精度问题； $a, b \leqslant X \leqslant 10^9$ ，乘积不超过 $10^{18}$ ）。 $b = 0$ 按题意视为 $+\infty$ ：有限比值总是更优；两个 $+\infty$ 相等，此时（以及比值并列时）按海拔取更高的起点。

下表是样例预处理出的目标城市（「—」表示东侧不存在）：

城市 $i$	1	2	3	4	5	6	7	8	9	10
海拔 $H_i$	4	5	6	1	2	3	7	8	9	10
小B（最近）	6	3	7	5	6	7	8	9	10	—
小A（次近）	2	6	8	6	7	8	9	10	—	—

注意城市 $1$ （海拔 4）：东侧距离为 $1$ 的候选有 $2$ （海拔 5）和 $6$ （海拔 3），距离并列时海拔低者算近，故小B 去 $6$ 、小A 去 $2$ 。再看城市 $3$ （海拔 6）： $2$ 在西侧根本不进候选——「目的地只在东侧」这一约束已由删除顺序天然保证；东侧最近的两个海拔是 $7$ （距离 1）和 $8$ （距离 2），故小B 去 $7$ 、小A 去 $8$ 。沿表逐列检查可以看到：每个目标都落在编号更大的列里。

最后用问题 1 串起全表。 $X_0 = 7$ 时枚举全部起点可得： $S=2$ 与 $S=4$ 的里程同为 $(2, 4)$ ，比值 $\tfrac{1}{2}$ 为全局最小；两者并列，按「海拔最高的出发城市」打破平手， $H_2 = 5 > H_4 = 1$ ，故输出 $S_0 = 2$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 开车旅行：海拔有序链表确定「最近 / 次近」，再倍增求任意起点出发的里程。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

struct Cand {
    ll id;
    ll dist;
    ll h;
};

bool cand_less(const Cand& a, const Cand& b) {
    if (a.dist != b.dist) return a.dist < b.dist;
    return a.h < b.h; // 距离相同时海拔低者算更近
}

ll n;
std::vector<ll> h;
std::vector<ll> na, nb; // na[i] / nb[i]：小A / 小B 从 i 向东要去的城市
std::vector<ll> west, east;

struct Tab {
    int nxt; // 走 2^k 步后到达的城市
    ll da;   // 这 2^k 步里小A 的里程
    ll db;   // 小B 的里程
};

std::vector<Tab> up; // up[(k*2+w)*(n+1)+i]

int main() {
    if (scanf("%lld", &n) != 1) return 0; // 空输入安全返回
    h.assign(n + 1, 0);
    for (ll i = 1; i <= n; i++) scanf("%lld", &h[i]);

    std::vector<ll> ord(n);
    for (ll i = 0; i < n; i++) ord[i] = i + 1;
    for (ll i = 0; i < n; i++) { // 按海拔升序
        for (ll j = i + 1; j < n; j++) {
            if (h[ord[j]] < h[ord[i]]) {
                ll t = ord[i]; ord[i] = ord[j]; ord[j] = t;
            }
        }
    }
    west.assign(n + 1, 0);
    east.assign(n + 1, 0);
    for (ll i = 0; i + 1 < n; i++) {
        east[ord[i]] = ord[i + 1];
        west[ord[i + 1]] = ord[i];
    }

    na.assign(n + 1, 0);
    nb.assign(n + 1, 0);
    Cand cand[4];
    for (ll i = 1; i <= n; i++) {
        ll cnt = 0;
        ll j = west[i];
        for (ll t = 0; t < 2; t++) { // 海拔方向两侧各取 2 个候选
            if (j) {
                cand[cnt].id = j;
                cand[cnt].dist = h[i] - h[j] > 0 ? h[i] - h[j] : h[j] - h[i];
                cand[cnt].h = h[j];
                cnt++;
                j = west[j];
            }
        }
        j = east[i];
        for (ll t = 0; t < 2; t++) {
            if (j) {
                cand[cnt].id = j;
                cand[cnt].dist = h[i] - h[j] > 0 ? h[i] - h[j] : h[j] - h[i];
                cand[cnt].h = h[j];
                cnt++;
                j = east[j];
            }
        }
        for (ll a = 0; a < cnt; a++) { // 手写插入排序，按 (距离, 海拔) 升序
            for (ll b = a + 1; b < cnt; b++) {
                if (cand_less(cand[b], cand[a])) {
                    Cand t = cand[a]; cand[a] = cand[b]; cand[b] = t;
                }
            }
        }
        nb[i] = (cnt > 0) ? cand[0].id : 0;
        na[i] = (cnt > 1) ? cand[1].id : 0;
        east[west[i]] = east[i]; // 删掉 i，链表里剩下的全是东边城市
        west[east[i]] = west[i];
    }

    ll log = 1;
    while ((1LL << log) < n) log++;
    if (log < 1) log = 1;

    up.assign((size_t)log * 2 * (n + 1), Tab());
    for (ll i = 1; i <= n; i++) {
        if (na[i]) {
            up[0 * 2 * (n + 1) + 0 * (n + 1) + i].nxt = (int)na[i];
            ll d = h[i] - h[na[i]];
            up[0 * 2 * (n + 1) + 0 * (n + 1) + i].da = d > 0 ? d : -d;
        }
        if (nb[i]) {
            up[0 * 2 * (n + 1) + 1 * (n + 1) + i].nxt = (int)nb[i];
            ll d = h[i] - h[nb[i]];
            up[0 * 2 * (n + 1) + 1 * (n + 1) + i].db = d > 0 ? d : -d;
        }
    }

    for (ll k = 1; k < log; k++) {
        ll pre = k - 1;
        for (ll w = 0; w < 2; w++) {
            ll w2 = (k == 1) ? (w ^ 1) : w; // 后一段的先开者只与 k 有关
            for (ll i = 1; i <= n; i++) {
                ll mid = up[(pre * 2 + w) * (n + 1) + i].nxt;
                if (mid) {
                    Tab& cur = up[(k * 2 + w) * (n + 1) + i];
                    Tab& a = up[(pre * 2 + w) * (n + 1) + i];
                    Tab& b = up[(pre * 2 + w2) * (n + 1) + mid];
                    cur.nxt = b.nxt;
                    cur.da = a.da + b.da;
                    cur.db = a.db + b.db;
                }
            }
        }
    }

    ll x0, m;
    scanf("%lld %lld", &x0, &m);
    std::vector<ll> qs(m), qx(m);
    for (ll i = 0; i < m; i++) scanf("%lld %lld", &qs[i], &qx[i]);

    // 问题 1：枚举起点找 a/b 最小的出发城市
    ll best_s = 1, best_a = 0, best_b = 0;
    for (ll s = 1; s <= n; s++) {
        ll a = 0, b = 0, cur = s, w = 0;
        for (ll k = log - 1; k >= 0; k--) {
            Tab& t = up[(k * 2 + w) * (n + 1) + cur];
            if (t.nxt && a + b + t.da + t.db <= x0) {
                a += t.da;
                b += t.db;
                cur = t.nxt;
                if (k == 0) w ^= 1; // 只有 2^0 = 1 步是奇数步，才换司机
            }
        }
        if (s == 1) {
            best_s = 1; best_a = a; best_b = b;
            continue;
        }
        bool take;
        if (b == 0) {
            take = (best_b == 0 && h[s] > h[best_s]); // 两个无穷大之间比海拔
        } else if (best_b == 0) {
            take = true; // 有限比值优于无穷大
        } else {
            ll lhs = a * best_b, rhs = best_a * b; // 交叉相乘比较 a/b
            take = (lhs < rhs) || (lhs == rhs && h[s] > h[best_s]);
        }
        if (take) {
            best_s = s; best_a = a; best_b = b;
        }
    }

    printf("%lld\n", best_s);
    for (ll i = 0; i < m; i++) { // 问题 2：逐个询问模拟
        ll s = qs[i], x = qx[i];
        ll a = 0, b = 0, cur = s, w = 0;
        for (ll k = log - 1; k >= 0; k--) {
            Tab& t = up[(k * 2 + w) * (n + 1) + cur];
            if (t.nxt && a + b + t.da + t.db <= x) {
                a += t.da;
                b += t.db;
                cur = t.nxt;
                if (k == 0) w ^= 1;
            }
        }
        printf("%lld %lld\n", a, b);
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 21:19
# update_at: 2026-10-01 21:39

import sys
from array import array

# 城市编号从 1 开始，0 统一表示「不存在 / 无法前进」的哨兵。


def choose_targets(h: list[int]) -> tuple[list[int], list[int]]:
    """返回 (na, nb)：na[i] / nb[i] 是小A / 小B 从 i 向东要去的城市。

    把城市按海拔排成双向链表后，距离最近、次近的候选只会藏在海拔相邻的
    至多 4 个城市里；按编号从西往东处理并删掉已处理城市，
    链表里剩下的恰好都是东边的城市。
    """
    n = len(h) - 1
    order = sorted(range(1, n + 1), key=lambda c: h[c])
    west = [0] * (n + 1)  # 海拔排序链表的左 / 右邻居
    east = [0] * (n + 1)
    for prev, cur in zip(order, order[1:]):
        east[prev] = cur
        west[cur] = prev

    na = [0] * (n + 1)
    nb = [0] * (n + 1)
    for i in range(1, n + 1):
        cand = []
        j = west[i]
        for _ in range(2):  # 海拔方向两侧各取 2 个候选
            if j:
                cand.append(j)
                j = west[j]
        j = east[i]
        for _ in range(2):
            if j:
                cand.append(j)
                j = east[j]
        # 距离相同时海拔低者算更近，所以排序后第 1 个给小B、第 2 个给小A
        cand.sort(key=lambda c: (abs(h[i] - h[c]), h[c]))
        nb[i] = cand[0] if cand else 0
        na[i] = cand[1] if len(cand) > 1 else 0
        east[west[i]] = east[i]  # 删掉 i，链表里剩下的全是东边城市
        west[east[i]] = west[i]
    return na, nb


def build_tables(na: list[int], nb: list[int], h: list[int]) -> tuple[int, list, list, list]:
    """建倍增表，返回 (log, nxt, da, db)。

    nxt[k][w][i]：从 i 出发、由 w（0=小A，1=小B）先开，走 2^k 步后到达的城市；
    da / db 同布局，记录这 2^k 步里两人各自的里程。
    后 2^(k-1) 步的先开者：k=1 时只剩 1 步要换人，k>=2 时走偶数步不换人。
    """
    n = len(h) - 1
    log = max(1, (n - 1).bit_length())  # 任意旅程步数 <= n-1，2^log 足够覆盖
    nxt = [[array('i', [0]) * (n + 1) for _ in range(2)] for _ in range(log)]
    da = [[array('q', [0]) * (n + 1) for _ in range(2)] for _ in range(log)]
    db = [[array('q', [0]) * (n + 1) for _ in range(2)] for _ in range(log)]

    for i in range(1, n + 1):
        if na[i]:
            nxt[0][0][i] = na[i]
            da[0][0][i] = abs(h[i] - h[na[i]])
        if nb[i]:
            nxt[0][1][i] = nb[i]
            db[0][1][i] = abs(h[i] - h[nb[i]])

    for k in range(1, log):
        pre = k - 1
        for w in range(2):
            w2 = w ^ 1 if k == 1 else w  # 后一段的先开者只与 k 有关
            for i in range(1, n + 1):
                mid = nxt[pre][w][i]
                if mid:
                    nxt[k][w][i] = nxt[pre][w2][mid]
                    da[k][w][i] = da[pre][w][i] + da[pre][w2][mid]
                    db[k][w][i] = db[pre][w][i] + db[pre][w2][mid]
    return log, nxt, da, db


def drive(s: int, x: int, log: int, nxt: list, da: list, db: list) -> tuple[int, int]:
    """从 s 出发最多开 x 公里，返回（小A总里程，小B总里程）。"""
    a = b = 0
    cur = s
    w = 0  # 第一天小A先开
    for k in range(log - 1, -1, -1):
        step = da[k][w][cur] + db[k][w][cur]
        if nxt[k][w][cur] and a + b + step <= x:
            a += da[k][w][cur]
            b += db[k][w][cur]
            cur = nxt[k][w][cur]
            if k == 0:  # 只有 2^0 = 1 步是奇数步，才换司机
                w ^= 1
    return a, b


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    h = [0] + [next(data) for _ in range(n)]
    x0 = next(data)
    m = next(data)
    queries = [(next(data), next(data)) for _ in range(m)]

    na, nb = choose_targets(h)
    log, nxt, da, db = build_tables(na, nb, h)

    # 问题 1：枚举起点找 a/b 最小的出发城市；b=0 视为无穷大，同值比海拔
    best_s = 1
    best_a, best_b = drive(1, x0, log, nxt, da, db)
    for s in range(2, n + 1):
        a, b = drive(s, x0, log, nxt, da, db)
        if b == 0:
            take = best_b == 0 and h[s] > h[best_s]  # 两个无穷大之间比海拔
        elif best_b == 0:
            take = True  # 有限比值优于无穷大
        else:
            lhs, rhs = a * best_b, best_a * b  # 交叉相乘比较 a/b，避免浮点误差
            take = lhs < rhs or (lhs == rhs and h[s] > h[best_s])
        if take:
            best_s, best_a, best_b = s, a, b

    out = [str(best_s)]
    for s, x in queries:  # 问题 2：逐个询问模拟
        a, b = drive(s, x, log, nxt, da, db)
        out.append(f'{a} {b}')
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

时间：预处理排序 + 建表 $O(N \log N)$ ；问题 1 枚举 $N$ 个起点 $O(N \log N)$ ；问题 2 每次询问 $O(\log N)$ ，合计 $O((N + M)\log N)$ 。
空间：三张 $\log N \times 2 \times (N+1)$ 的表， $O(N \log N)$ 。

总结

模型：向东行驶 + 确定性选择规则 ⇒ 路径由（起点，先开者）唯一决定 ⇒ 倍增。
两个易错点：
1. 换司机只发生在奇数步的段——倍增拼接时 $k=1$ 要交换先开者， $k \geqslant 2$ 不交换， $k=0$ 走完交换；
2. 距离并列按海拔低者算近；比值并列（含两个 $+\infty$ ）按起点海拔高者输出。
链表删除顺序（按编号从西往东处理、处理完即删）是「目的地只在东侧」这一约束的零成本实现。

图示解析

从样例表到第一次跳跃

以 $S=1,\ X_0=7$ 为例演示 drive 的二进制分解（ $\log = 4$ ）：

尝试 $k$	段长	是否成行	累计 (A, B)	当前城市 / 先开者
3	8 步	表项为 0（走不满 8 步），跳过	(0, 0)	1 / A
2	4 步	1→2→3→8→9，合计 +5 $\leqslant 7$ ，跳	(3, 2)	9 / A
1	2 步	9 以东走不满 2 步，表项为 0，跳过	(3, 2)	9 / A
0	1 步	9 的次近不存在，表项为 0，跳过	(3, 2)	结束

逐行对照：高位先试大步，能跳则跳，剩余距离交给低位； $k=2$ 一次跳完 4 步后里程已定为 $(3, 2)$ ，低位全部无处可走。因此 $S=1$ 时总里程为 $(3, 2)$ ，与样例第一行一致；由上文起点枚举，全局最优是 $S_0 = 2$ （ $S=2$ 与 $S=4$ 并列比值 $\tfrac{1}{2}$ ，海拔更高者胜出）。

小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i 的海拔高度为 $H\_i$ 。

城市 i 和城市 j 之间的距离 d[i,j] 恰好是这两个城市海拔高度之差的绝对值，即 $d\[i,j\]=|H\_i-H\_j|$ 。

旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。每个人每天均会从一个城市出发走到另一个城市。

他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。

小A和小B的驾驶风格不同，小B总是沿着前进方向选择一个最近的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。

如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出X公里，他们就会结束旅行。

在启程之前，小A想知道两个问题：

1、对于一个给定的 $X=X\_0$ ，从哪一个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小（如果小B的行驶路程为0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

2、对任意给定的 $X=X\_i$ 和出发城市 $S\_i$ ，求出小A开车行驶的路程总数以及小B行驶的路程总数。

输入格式

第一行包含一个整数 N,表示城市的数目。

第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即 $H\_1,H\_2,…,H\_n$ ,且每个 $H\_i$ 都是不同的。

第三行包含一个整数 $X\_0$ 。

第四行为一个整数 M,表示给定 M 组 $S\_i$ 和 $X\_i$ 。

接下来的 M 行,每行包含 2 个整数 $S\_i$ 和 $X\_i$ ,表示从城市 $S\_i$ 出发,最多行驶 $X\_i$ 公里。

输出格式

输出共 M+1 行。

第一行包含一个整数 $S\_0$ ,表示对于给定的 $X\_0$ ,从编号为 $S\_0$ 的城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小。

接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 $S\_i$ 和 $X\_i$ 下小 A 行驶的里程总数和小 B 行驶的里程总数。

数据范围

$1 \le N \le 10^5$ ,
$1 \le M \le 10^4$ ,
$-10^9 \le H\_i \le 10^9$ ,
$0 \le X\_0 \le 10^9$ ,
$1 \le S\_i \le N$ ,
$0 \le X\_i \le 10^9$ ，
数据保证 $H\_i$ 互不相同。

输入样例：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
1410
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7

输出样例：

text

来源

《算法竞赛进阶指南》
acwing 可能含有视频讲解

开车旅行

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

从样例表到第一次跳跃