前言

本文中的对数函数默认底数为

2

。
2025 年 5 月 17 日，发现代码贴错了，已改正。
2025 年 5 月 17 日，人名字体更改了。
2025 年 5 月 18 日，时间复杂度的符号更改了。

题意概述

有

n(1 \le n \le 10^5)

座城市，从西至东依次编号

1,2,\cdots,n

，海拔各不相同，为

h_1,h_2,\cdots,h_n(|h_i| \le 10^9)

。城市

i

与城市

j

的距离为

d_{i,j} = |h_i - h_j|

。旅行中，小 A 与小 B 依次开车，第一天小 A 开车，之后每天轮换一次，一直向东行驶。小 A 总是开往前进方向上第二近的城市，小 B 总是开往前进方向上第一近的城市（如果距离相同，则认为海拔更低的城市是更近的）。当任何一人无法按自己的策略前进，或前进后的行驶总距离大于

x

，则不继续前进，结束旅行。
问：

对于给定的 $x$ ，从哪个城市出发小 A 行驶的总距离与小 B 行驶的总距离的比值最小（若小 B 行驶的总距离为 $0$ ，则比值为无穷大；若多个比值相等，则答案为海拔最高的城市）？（共询问 $1$ 次）
对于给定的出发城市 $s$ 与 $x$ ，求小 A 行驶的总距离与小 B 行驶的总距离。（共询问 $m(1 \le m \le 10^5)$ 次）

想看题目点这里：题目链接。

正解思路

首先，这道题是一道静态查询的题目，解决这类问题有一个很好的方法——预处理。很显然，要想解决这道题，小 A 和小 B 的行驶策略是很重要的。我们需要知道，已知当前的城市，小 A 和小 B 行驶到的下一个城市是哪一座以及这次行驶的距离（先不管得知之后该如何用，至少在目前的思路还是需要知道的）？
为了解决这个问题，首先就需要了解小 A 与小 B 的策略。

小 A 与小 B 的行驶策略

先看小 B，小 B 总是开往前进方向上第一近的城市编号。即：若当前城市编号为

i

，则寻找满足

|h_i - h_j|

最小的

j

，且满足

i < j \le n

（当然，如有多个，选取

h_j

最大的）。题目中有一句“各个城市的海拔高度各不相同”，这就说明，满足

|h_i - h_j|

最小，且满足

i < j \le n

的

j

，最多有两个（一个

h_j < h_i

，另一个

h_j > h_i

）。
更进一步，这样的

j

会出现在哪儿呢？不难发现，若将满足

i < j \le n

的

j

分成两组，一组是满足

i < j \le n

且

h_j < h_i

（第一组），另一组是满足

i < j \le n

且

h_j > h_i

（第二组），则答案要么是第一组中的

h_j

的最大值所对应的

j

（如果有的话），要么是第二组中的

h_j

的最小值所对应的

j

（如果有的话）。所以，寻找小 B 行驶的下一个城市，就需要寻找满足

i < j \le n

且

h_j < h_i

中的

h_j

的最大值所对应的

j

和满足

i < j \le n

且

h_j > h_i

中的

h_j

的最小值所对应的

j

后再比较一下，选出距离最小的

j

。
再看小 A，同理可得：寻找小 A 行驶的下一个城市，就需要寻找满足

i < j \le n

且

h_j < h_i

中的

h_j

的最大值与次大值所对应的

j

和满足

i < j \le n

且

h_j > h_i

中的

h_j

的最小值与次小值所对应的

j

后再比较一下，选出距离次小的

j

。

输入及预处理小 A 与小 B 行驶的下一个城市

方法是有了，但是要如何去做呢？输入完了之后，如果直接循环

i

后再去循环

j

的话，时间复杂度是

O(n^2)

级的。那该怎么办呢？我们想到，可以直接全部按

h_i

的大小排序（做结构体保留原下标），然后上面（小 A 与小 B 的策略）的四个数就都在它所在的左边和右边了两个（如果存在的话）——吗？还有一个问题，就是要满足

i < j \le n

，可是在它旁边的可不一定是满足

i < j

的。那怎么办？要保证序列有序，又不能考虑

j < i

的情况，怎么办呢？
我们发现，当

i = 1

时，不存在

j < i

的情况，所以显然当

i = 1

时答案是正确的。当

i > 1

时，相比于

i

是此时的

i - 1

的时候，可选的序列再加上此时的

i

本身少了

i - 1

。所以是不是只要把

i - 1

对应的元素删掉就好了呢？当然，直接删除的时间复杂度是

O(n)

，所以不可以直接删除。但是有一种线性数据结构，支持常数级的删除操作，它就是链表！所以将

h_i

排序后再建一个链表（可以手写，如果不是手写的话，那就要令存一个

h

数组，因为数组模拟的链表删除元素并没有将其真的删除，即便它已经不在链表中了，但它的值还在数组中，在后面回答问题一的时候，若两个比值相等，还要判断哪个城市的高度更高），每次将此次的

i

处理完存到数组中后将对应的元素删掉就好了（上面的

i

，

j

都指的是原数组的下标）。
这部分只剩下一件事了：如何常数级地找到原来下标

i

所对应的元素呢？这也很简单，建一个数组，表示原数组的这个下标在排序后的数组里的下标，遍历一遍链表，每次将值储存好就行了。
所以，这部分的时间复杂度就是：输入

O(n)

，排序

O(n \log n)

，遍历

O(n)

，求出小 A 与小 B 的下一个城市序号及距离

O(n)

，所以这部分总的时间复杂度就是

O(n \log n)

。
贴上相关部分代码：

CPP

cin >> n;
for(int i = 1; i <= n; i ++) {
    cin >> h[i].hh;
    h[i].ix = i;
}
sort(h + 1, h + n + 1, cmp1);//对 h 数组排序
for(int i = 1; i <= n; i ++) {
    h[i].prv = i - 1;
    h[i].nxt = i + 1;
    ixh[h[i].ix] = i;//方便 O(1) 找到原数组编号为 h[i].ix 的元素在排序后数组的下标（i）
}
h[n].nxt = 0;
for(int i = 1; i <= n; i ++) {
    top = 0;
    temp = ixh[i];
    Work(h[temp].prv);
    Work(h[h[temp].prv].prv);
    Work(h[temp].nxt);
    Work(h[h[temp].nxt].nxt);
    sort(t + 1, t + top + 1, cmp2);//排序
    if(top >= 1) {//至少有一个可以到达的城市，则小 B 的策略可以满足
        b[i] = h[t[1]].ix;
        disb[i] = Abs(h[t[1]].hh - h[temp].hh);
    }
    if(top >= 2) {//至少有两个可以到达的城市，则小 A 的策略可以满足
        a[i] = h[t[2]].ix;
        disa[i][0] = Abs(h[t[2]].hh - h[temp].hh);
    }
    if(h[temp].nxt) h[h[temp].nxt].prv = h[temp].prv;
    if(h[temp].prv) h[h[temp].prv].nxt = h[temp].nxt;
}

计算倍增数组

那接下来，该如何用呢？假设在城市

i

小 A 的行驶目标为

a_i

、行驶路程为

disa_i

，小 B 的行驶目标为

b_i

、行驶路程为

disb_i

。那么就模拟吧，小 A 行驶一天、小 B 行驶一天为一组，一组一组地行驶，最后特判一下小 A 单独行驶一天，然后求出答案即可。但是，时间复杂度：问题一的时间复杂度是

O(n^2)

，问题二的时间复杂度是

O(nm)

，共

O((n+m)n)

。显然，超时了。
接下来考虑优化，一组一组地行驶太慢了，能不能使用二进制的方式从大往小枚举呢？但是这样就需要预处理从城市

i

开始行驶

2^j

天后的城市编号与行驶的距离。倍增的思想已经呼之欲出了。定义

ab_{i,j}

、

disab_{i,j}

分别表示从城市

i

开始两人一起行驶

2^j

组后所在的城市编号与一共行驶的距离。那么

ab_{i,j}

的求法如下：

ab_{i,j} = \begin{cases} b_{a_i} & j = 0 \\ ab_{ab_{i,j-1},j-1} & j > 0 \end{cases}

相应地，

disab_{i,j}

的求法如下：

disab_{i,j} = \begin{cases} disa_i + disb_{a_i} & j = 0 \\ disab_{i,j-1} + disab_{ab_{i,j-1},j-1} & j > 0 \end{cases}

当然，以上

disab_{i,j}

求法针对的都是能够行驶的情况，所以使用的时候记得要判断

ab_{i,j-1}

是否存在（不为初值

0

，因为凡是能够到达的，数组中一定是一个正整数）。
但是我们发现，使用的时候需要同时求出小 A 与小 B 的行驶路程，但是显然小 A 行驶的路程加上小 B 行驶的流程就是他们两个总共行驶的路程。所以只需要存小 A 的路程就足够了（当然，你要存小 B 的也不是不可以）。改一下定义。原来的

disa_i

改成

disa_{i,j}

，定义

disa_{i,j}

表示从城市

i

开始两人一起行驶

2^j

组后小 A 的行驶的距离（这次改完定义后，前面所有的

disa_i

都要改成

disa_{i,0}

），则经过刚才链表那部分的操作后，已经求出了

disa_{i,0}

（即原来的“

disa_i

”）。所以

disa_{i,j}=disa_{i,j-1}+disa_{ab_{i,j-1},j-1}(j>0)

。
时间复杂度显然就是

O(n \log n)

。但是要注意，循环的时候要先循环

j

（外循环）、再循环

i

（内循环），否则数组里的数据就会出问题。
贴上相关部分代码：

CPP

for(int i = 1; i <= n; i ++) {
    ab[i][0] = b[a[i]];
    disab[i][0] = disa[i][0] + disb[a[i]];
}
k = log2(n);//提前存储一下
for(int j = 1; j <= k; j ++) {
    for(int i = 1; i <= n; i ++) {
        ab[i][j] = ab[ab[i][j - 1]][j - 1];
        disab[i][j] = disab[i][j - 1] + disab[ab[i][j - 1]][j - 1];
        disa[i][j] = disa[i][j - 1] + disa[ab[i][j - 1]][j - 1];
    }
}

回答询问

倍增数组都预处理完了，接下来就可以回答询问了。其实前面也提到过回答询问的方法。其实询问核心只有一种，就是给定出发城市

s

与路程限制

x

，求小 A 的行驶路程与小 B 的行驶路程。问题一只不过是这种问题（问题二）的一种变体。所以，问题二是关键。
先看问题二，其实倍增数组预处理完了之后就很简单了，只要从大往小尝试行驶的组数以二为底数的幂指数，满足条件就行驶，累加总路程与小 A 行驶的路程，最后记得特判小 A 单独再行驶一天的情况，总路程减去小 A 行驶的路程就是小 B 行驶的路程。
那么问题一就很简单了，枚举出发城市

s

，每次按照问题二的方式进行求解，在按照题目的要求比较比值大小即可。这里有两种方式，一种是相除（用 double 或 long double 来存储）后比较大小，另一种是分子与分母分别交叉相乘，比较大小。但是第二种方式的乘积可能要用 int128 的类型来存储，因为乘积的极限是

10^{28}

次方级的，long long 存不下（说起存储，温馨提示：本题建议大部分变量用 long long 存储）。一定要注意，不论是哪一种方法，都要先判断分母是

0

的情况（方法一要相除，所以要判断分母是否是

0

；方法二要分子分母交叉相乘，则如果两个分数是

\frac{p}{q}

（

p \ge 0

，

q > 0

）和

\frac{0}{0}

的形式的话，此时的两个乘积就都是

0

，但是显然在题目的要求下

\frac{p}{q} < \frac{0}{0}

，所以要先判断分母是

0

的情况）。
那时间复杂度就是：问题一

O(n \log n)

，问题二

O(m \log n)

，总的回答询问的时间复杂度就是

O((n + m) \log n)

。
最后，总的时间复杂度就是

O((n + m) \log n)

，空间复杂度就是

O(n \log n)

，通过！
贴上相关部分代码：

CPP

cin >> x;
for(int i = 1; i <= n; i ++) {
    Calc(i, x);
    if(i == 1) Ans(i, lena, lenb);//目前还没有任何答案，直接记录下来
    else {
        if(!lenb) {
            if((!ansb) && h[ixh[i]].hh > h[ixh[ansi]].hh) Ans(i, lena, lenb);//两个比值都是无穷大，比高度
        }
        else {
            if(!ansb) Ans(i, lena, lenb);//新的比值不是无穷大，而目前的答案的比值是无穷大
            else {//两个比值都不是无穷大
                __int128 answ = __int128(ansa) * __int128(lenb);
                __int128 lenw = __int128(lena) * __int128(ansb);
                if(lenw < answ) Ans(i, lena, lenb);//新的比值比目前的答案的比值更小
                else if(lenw == answ && h[ixh[i]].hh > h[ixh[ansi]].hh) Ans(i, lena, lenb);//两个比值相等，比高度
            }
        }
    }
}
cout << ansi << endl;
cin >> m;
while(m --) {
    cin >> s >> x;
    Calc(s, x);
    cout << lena << " " << lenb << endl;
}

思路梳理

最后梳理一下思路：

预处理
- 输入 $n$ 并循环输入原数组，保留原数组下标，按高度排序
- 用数组模拟双向链表，并存储原数组元素在排序后数组中的下标
- 循环从 $1$ $1$ 到 $n$ $n$ 枚举原数组的下标 $i$ $i$
  - 找到原数组中下标为 $i$ 的元素在排序后数组中的下标
  - 找到它在链表中的前驱、前驱的前驱、后继、后继的后继（如果有的话），并对找到它们中距离循环枚举的城市最短和次短的城市（如果有的话），并将这个城市与其与循环枚举的城市的距离存储下来
  - 将循环所枚举的元素从用数组模拟的链表中删除
- 循环城市编号 $i$ $i$ ，从 $1$ $1$ 到 $n$ $n$
  - 处理出 $ab_{i,0}=b_{a_i}$ ， $disab_{i,0}=disa_{i,0}+disb_{a_i}$
- 循环倍增数组中的第二维 $j$ $j$ ，从 $1$ $1$ 到 $\lfloor \log n \rfloor$ $⌊ lo g n ⌋$
  - 循环倍增数组的第一维 $i$ $i$ ，从 $1$ $1$ 到 $n$ $n$
    - 处理出 $disa_{i,j}=disa_{i,j-1}+disa_{ab_{i,j-1},j-1}$ ， $ab_{i,j} = ab_{ab_{i,j-1},j-1}$ ， $disab_{i,j} = disab_{i,j-1}+disab_{ab_{i,j-1},j-1}$
回答询问
- 问题一
  - 输入 $x$
  - 循环枚举出发城市 $i$ $i$
    - 循环枚举行驶的组数的幂指数（底数为 $2$ $2$ ）
      - 尝试两人行驶 $2^j$ 组（在满足条件的情况下），并记录小 A 的行驶路程与两人的行驶路程
    - 特判小 A 单独行驶一天的情况
    - 计算小 B 行驶的路程，即两人的行驶路程减去小 A 的行驶路程
    - 按题目要求比较答案，与现有答案比较，选出使小 A 与小 B 行驶的路程的比值最小的出发城市（若相等，则比较高度），如果是这次新的答案，就将其记录在现有的答案中
- 问题二
  - 共有 $m$ $m$ 次询问，循环 $m$ $m$ 次
    - 循环枚举行驶的组数的幂指数（底数为 $2$ $2$ ）
      - 尝试两人行驶 $2^j$ 组（在满足条件的情况下），并记录小 A 的行驶路程与两人的行驶路程
    - 特判小 A 单独行驶一天的情况
    - 输出答案

代码

我们发现在思路中，有一些重复的步骤，比如：

循环枚举行驶的组数的幂指数（底数为 $2$ $2$ ）
- 尝试两人行驶 $2^j$ 组（在满足条件的情况下），并记录小 A 的行驶路程与两人的行驶路程
特判小 A 单独行驶一天的况

所以，可以将这样的步骤封装成一个函数。
好了，贴代码。

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, ixh[100010], t[100010], top, temp, a[100010], disa[100010][17], b[100010], disb[100010], ab[100010][17], disab[100010][17], m, x, s, lena, lenb, ansa, ansb, ansi;
struct node {
    int hh, ix, prv, nxt;//高度、原数组下标、前驱、后继
}h[100010];
int Abs(int u) {
    return (u > 0) ? u : (-u);
}
bool cmp1(node u, node v) {//排序比较函数 1
    return u.hh < v.hh;//按高度从小往大排序
}
bool cmp2(int u, int v) {//排序比较函数 2
    if(Abs(h[u].hh - h[temp].hh) != Abs(h[v].hh - h[temp].hh)) return Abs(h[u].hh - h[temp].hh) < Abs(h[v].hh - h[temp].hh);//如果差的绝对值不相等，就按差的绝对值从小往大排序
    return h[u].hh < h[v].hh;//否则，高度小的距离更近，按高度从小往大（虽然最多只有两个）
}
void Work(int u) {
    if(u) t[++top] = u;
}
void Calc(int ss, int xx) {//计算从城市 ss 出发，在总路程不超过 xx 的情况下小 A 行驶的路程与小 B 行驶的路程
    lena = lenb = 0;//小 A 的路程与小 B 的路程（先计算一共的路程，再减去小 A 的路程得出小 B 的路程）初值为 0
    for(int i = k; i >= 0; i --) {
        if(ab[ss][i] && lenb + disab[ss][i] <= xx) {
            lenb += disab[ss][i];
            lena += disa[ss][i];
            ss = ab[ss][i];
        }
    }
    if(a[ss] && lenb + disa[ss][0] <= xx) {//特判小 A 最后单独行驶一天的情况
        lenb += disa[ss][0];
        lena += disa[ss][0];
        ss = a[ss];
    }
    lenb -= lena;//求出小 B 的路程
}
void Ans(int u, int v, int w) {//记录答案
    ansi = u;
    ansa = v;
    ansb = w;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> h[i].hh;
        h[i].ix = i;
    }
    sort(h + 1, h + n + 1, cmp1);//对 h 数组排序
    for(int i = 1; i <= n; i ++) {
        h[i].prv = i - 1;
        h[i].nxt = i + 1;
        ixh[h[i].ix] = i;//方便 O(1) 找到原数组编号为 h[i].ix 的元素在排序后数组的下标（i）
    }
    h[n].nxt = 0;
    for(int i = 1; i <= n; i ++) {
        top = 0;
        temp = ixh[i];
        Work(h[temp].prv);
        Work(h[h[temp].prv].prv);
        Work(h[temp].nxt);
        Work(h[h[temp].nxt].nxt);
        sort(t + 1, t + top + 1, cmp2);//排序
        if(top >= 1) {//至少有一个可以到达的城市，则小 B 的策略可以满足
            b[i] = h[t[1]].ix;
            disb[i] = Abs(h[t[1]].hh - h[temp].hh);
        }
        if(top >= 2) {//至少有两个可以到达的城市，则小 A 的策略可以满足
            a[i] = h[t[2]].ix;
            disa[i][0] = Abs(h[t[2]].hh - h[temp].hh);
        }
        if(h[temp].nxt) h[h[temp].nxt].prv = h[temp].prv;
        if(h[temp].prv) h[h[temp].prv].nxt = h[temp].nxt;
    }
    for(int i = 1; i <= n; i ++) {
        ab[i][0] = b[a[i]];
        disab[i][0] = disa[i][0] + disb[a[i]];
    }
    k = log2(n);//提前存储一下
    for(int j = 1; j <= k; j ++) {
        for(int i = 1; i <= n; i ++) {
            ab[i][j] = ab[ab[i][j - 1]][j - 1];
            disab[i][j] = disab[i][j - 1] + disab[ab[i][j - 1]][j - 1];
            disa[i][j] = disa[i][j - 1] + disa[ab[i][j - 1]][j - 1];
        }
    }
    cin >> x;
    for(int i = 1; i <= n; i ++) {
        Calc(i, x);
        if(i == 1) Ans(i, lena, lenb);//目前还没有任何答案，直接记录下来
        else {
            if(!lenb) {
                if((!ansb) && h[ixh[i]].hh > h[ixh[ansi]].hh) Ans(i, lena, lenb);//两个比值都是无穷大，比高度
            }
            else {
                if(!ansb) Ans(i, lena, lenb);//新的比值不是无穷大，而目前的答案的比值是无穷大
                else {//两个比值都不是无穷大
                    __int128 answ = __int128(ansa) * __int128(lenb);
                    __int128 lenw = __int128(lena) * __int128(ansb);
                    if(lenw < answ) Ans(i, lena, lenb);//新的比值比目前的答案的比值更小
                    else if(lenw == answ && h[ixh[i]].hh > h[ixh[ansi]].hh) Ans(i, lena, lenb);//两个比值相等，比高度
                }
            }
        }
    }
    cout << ansi << endl;
    cin >> m;
    while(m --) {
        cin >> s >> x;
        Calc(s, x);
        cout << lena << " " << lenb << endl;
    }
    return 0;
}

当然，在上面代码中，比较比值的部分你也可以这样写：

CPP

if(i == 1 || (lenb && ((!ansb) || (ansb && (lenw < answ || (lenw == answ && h[ixh[i]].hh > h[ixh[ansi]].hh)))) || ((!lenb) && (!ansb) && h[ixh[i]].hh > h[ixh[ansi]].hh))) Ans(i, lena, lenb);

我的提交记录

后记

本题代码较长，实现细节较多，但还是自己手打，不要抄代码。
最后祝愿大家在美好的绿色方块中通过此题！

P1081 题解

文章操作

前言

题意概述

正解思路

小 A 与小 B 的行驶策略

输入及预处理小 A 与小 B 行驶的下一个城市

计算倍增数组

回答询问

思路梳理

代码

我的提交记录

后记

相关推荐

评论

P1081 题解

文章操作

前言

题意概述

正解思路

小 A 与 小 B 的行驶策略

输入及预处理小 A 与小 B 行驶的下一个城市

计算倍增数组

回答询问

思路梳理

代码

我的提交记录

后记

相关推荐

评论

小 A 与小 B 的行驶策略