P1081 题解

MasterArcherSkeleton · 2025-03-03 13:09:01 · 题解

前言

本文中的对数函数默认底数为 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，则不继续前进，结束旅行。
问：

1. 对于给定的 x，从哪个城市出发小 A 行驶的总距离与小 B 行驶的总距离的比值最小（若小 B 行驶的总距离为 0，则比值为无穷大；若多个比值相等，则答案为海拔最高的城市）？（共询问 1 次）
2. 对于给定的出发城市 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)。
贴上相关部分代码：

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;
}

相关函数：

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;
}

相关数据结构：

int n, ixh[100010], t[100010], top, temp, a[100010], disa[100010][17], b[100010], disb[100010];
struct node {
    int hh, ix, prv, nxt;//高度、原数组下标、前驱、后继
}h[100010];

计算倍增数组

那接下来，该如何用呢？假设在城市 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} 的求法如下：

相应地，disab_{i,j} 的求法如下：

当然，以上 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（内循环），否则数组里的数据就会出问题。
贴上相关部分代码：

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];
    }
}

相关数据结构：

int n, k, a[100010], disa[100010][17], b[100010], disb[100010], ab[100010][17], disab[100010][17];

回答询问

倍增数组都预处理完了，接下来就可以回答询问了。其实前面也提到过回答询问的方法。其实询问核心只有一种，就是给定出发城市 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)，通过！
贴上相关部分代码：

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;
}

相关函数：

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;
}

相关数据结构：

int n, k, ixh[100010], a[100010], disa[100010][17], ab[100010][17], disab[100010][17], m, x, s, lena, lenb, ansa, ansb, ansi;

思路梳理

最后梳理一下思路：

• 预处理

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

      代码

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

• 循环枚举行驶的组数的幂指数（底数为 2）

  • 尝试两人行驶 2^j 组（在满足条件的情况下），并记录小 A 的行驶路程与两人的行驶路程

• 特判小 A 单独行驶一天的况

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

#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;
}

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

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);

我的提交记录

我的提交记录

后记

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