Moe's CF Life

哈喵~ 主人，今天我们来看一道 Codeforces 上的题目，叫做 Scuza！这道题就像是帮一位叫 Timur 的小伙子计算他能爬多高的楼梯，是不是很有趣呀？让本喵带你一步一步解开它吧，喵~

题目大意

这道题是说，有一个叫做 Timur 的人，他要去爬一个有 $n$ 阶的楼梯。第 $i$ 阶台阶的高度是 $a_i$ 。注意哦，这个 $a_i$ 不是台阶距离地面的高度，而是它比前一阶高出的部分。第一阶台阶就是比地面高 $a_1$ 。

Timur 有 $q$ 个问题，每个问题都给他一个整数 $k_i$ ，代表他这次的腿长。他能爬上第 $j$ 阶台阶的条件是，他的腿长必须不小于第 $j$ 阶台阶的高度，也就是 $k_i \ge a_j$ 。

重要的一点是，要爬到第 $j$ 阶，Timur 必须能爬上从第 1 阶到第 $j$ 阶的所有台阶。这意味着，他的腿长 $k_i$ 必须大于等于从第 1 阶到第 $j$ 阶中最高的那一阶的高度。

对于每个问题 $k_i$ ，我们需要计算出 Timur 能达到的最大总高度。每个问题都是独立的哦。

举个例子，喵~ 如果台阶高度是 [1, 2, 1, 5]，腿长是 2。

他能爬第 1 阶吗？可以，因为 2 >= 1。
他能爬第 2 阶吗？可以，因为 2 >= 2。
他能爬第 3 阶吗？可以，因为 2 >= 1。
他能爬第 4 阶吗？不行哦，因为 2 < 5。所以，他最多只能爬到第 3 阶。能达到的总高度就是前 3 阶的高度之和：1 + 2 + 1 = 4。

解题思路

这道题的关键在于，对于一个给定的腿长 $k$ ，Timur 能爬到的最高台阶是由他一路上遇到的最难（也就是最高）的台阶决定的。如果他连路上最高的那个台阶都迈不过去，那后面的也就不用想啦，喵~

所以，对于每个询问的腿长 $k$ ，我们要找到一个最大的索引 $p$ ，使得 Timur 能够爬上从第 1 阶到第 $p$ 阶的所有台阶。这个条件等价于，他的腿长 $k$ 必须大于或等于从第 1 阶到第 $p$ 阶中所有台阶高度的最大值。

设 max_a[p] = max(a_1, a_2, ..., a_p)。 Timur 能爬到第 $p$ 阶的充要条件是： $k \ge \text{max_a}[p]$ 。

我们的目标就是找到这个最大的 $p$ ，然后计算此时的总高度，也就是 sum[p] = a_1 + a_2 + ... + a_p。

因为有很多个询问，每次都从头计算会很慢，所以我们可以先做一些预处理，喵~

预处理前缀和 (Prefix Sum)：我们可以创建一个数组 prefix_sum，其中 prefix_sum[i] 存储从第 1 阶到第 $i$ 阶的总高度。这样就能在 O(1) 时间内得到任意前 $i$ 阶的总高度啦。 prefix_sum[i] = a_1 + a_2 + ... + a_i
预处理前缀最大值 (Prefix Maximum)：我们再创建一个数组 prefix_max，其中 prefix_max[i] 存储从第 1 阶到第 $i$ 阶中最高的台阶的高度。 prefix_max[i] = max(a_1, a_2, ..., a_i)

这两个数组都可以在 O(n) 的时间内计算出来。

现在，对于每个询问的腿长 $k$ ，问题就变成了：在 prefix_max 数组中，找到一个最大的索引 $p$ ，使得 prefix_max[p] <= k。

注意到 prefix_max 数组有一个非常好的性质：它是非递减的。也就是说 prefix_max[i] <= prefix_max[i+1]。这是因为 prefix_max[i+1] = max(prefix_max[i], a_{i+1})，所以它肯定不会变小。

对于一个非递减的数组，我们可以用二分查找来快速找到我们想要的那个位置！这可比一个一个地遍历快多啦，喵~

我们可以使用 C++ STL 中的 std::upper_bound 函数。upper_bound(prefix_max.begin(), prefix_max.end(), k) 会返回数组中第一个严格大于 $k$ 的元素的位置。

假设 upper_bound 返回的位置（迭代器）指向索引 p。这意味着 prefix_max 数组中，从索引 0 到 p-1 的所有元素都小于或等于 $k$ 。
这不就正好是我们想要的吗！Timur 最多可以爬到第 $p$ 阶（索引是 p-1）。
那么，他能达到的总高度就是 prefix_sum[p-1]。
如果 upper_bound 返回的是数组的起始位置（即 p=0），说明连第一阶 prefix_max[0] 都比 $k$ 大，Timur 一步也上不去，所以高度是 0。

这样，预处理的时间复杂度是 O(n)，每个查询的时间复杂度是 O(log n)。总的时间复杂度就是 O(n + q log n)，完全可以接受，喵~

哦对了，题目提醒我们答案可能会很大，所以要用 64 位整型（比如 C++ 的 long long）来存储总高度哦！

题解

下面就是完整的 C++ 代码啦，本喵加了一些注释，方便主人理解~

cpp

#include <iostream>
#include <vector>
#include <numeric> // std::accumulate
#include <algorithm> // std::max, std::upper_bound
#include <iterator> // std::distance

void solve() {
    int n, q;
    std::cin >> n >> q;

    // 用来存储每一步需要迈过的最大高度
    std::vector<long long> prefix_max(n);
    // 用来存储到达某一步的总高度
    std::vector<long long> prefix_sum(n);

    long long current_max = 0;
    long long current_sum = 0;

    // O(n) 预处理
    for (int i = 0; i < n; ++i) {
        long long val;
        std::cin >> val;
        current_sum += val; // 累加总高度
        current_max = std::max(current_max, val); // 更新到目前为止遇到的最高台阶
        prefix_sum[i] = current_sum;
        prefix_max[i] = current_max;
    }

    // 处理 q 个查询
    for (int i = 0; i < q; ++i) {
        long long k;
        std::cin >> k;

        // 使用二分查找 (upper_bound) 找到第一个比 k 大的前缀最大值的位置
        // 这意味着在这个位置之前的所有台阶，Timur 都能爬上去
        auto it = std::upper_bound(prefix_max.begin(), prefix_max.end(), k);

        // 计算这个位置对应的索引，也就是能爬的台阶数量
        int count = std::distance(prefix_max.begin(), it);

        if (count == 0) {
            // 如果 count 是 0，说明第一阶都爬不上去
            std::cout << 0;
        } else {
            // 否则，答案就是能爬上的所有台阶的总高度
            // 因为 count 是数量，所以对应的索引是 count - 1
            std::cout << prefix_sum[count - 1];
        }

        if (i < q - 1) {
            std::cout << " ";
        }
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍

这道题用到了几个很基础但又非常重要的算法思想，让本喵来给你介绍一下吧！

前缀和 (Prefix Sum)
- 是什么：前缀和是一种预处理技术。对于一个数组 A，它的前缀和数组 S 的定义是 S[i] = A[0] + A[1] + ... + A[i]。
- 有什么用：它能让我们在 O(1) 的时间内查询任意一个前缀区间的总和。比如在这道题里，我们想知道爬完前 p 阶的总高度，直接查 prefix_sum[p-1] 就好啦，不需要再从头加一遍。
前缀最大值 (Prefix Maximum)
- 是什么：和前缀和类似，前缀最大值数组 M 的定义是 M[i] = max(A[0], A[1], ..., A[i])。
- 有什么用：它能让我们在 O(1) 的时间内查询任意一个前缀区间的最大值。在这道题里，它帮助我们快速判断 Timur 的腿长是否足够爬到第 i 阶。
- 重要性质：前缀最大值数组一定是非递减的，这个性质是能够使用二分查找的关键。
二分查找 (Binary Search)
- 是什么：二分查找是一种在有序数组中查找特定元素的搜索算法。它每次都检查数组中间的元素，如果中间元素不是目标值，就根据大小关系排除掉一半的元素，然后在剩下的一半中继续查找。
- 有什么用：它的时间复杂度是 O(log n)，比线性搜索的 O(n) 快得多，特别适合处理大规模数据的查询。
- std::upper_bound：这是 C++ 标准库里一个非常有用的函数。它在有序区间 [first, last) 中进行二分查找，返回第一个大于指定值的元素的位置。在本题中，我们用它来高效地找到 Timur 无法逾越的第一个台阶，从而确定他能爬到的极限位置。

好啦，这道题的讲解就到这里啦！希望主人能够明白，喵~ 如果还有不懂的地方，随时可以再来问本喵哦！

题目大意 ​

解题思路 ​

题解 ​

知识点介绍 ​

题目大意

解题思路

题解

知识点介绍