E. Bus Video System - 题解

比赛与标签

比赛: Codeforces Round 481 (Div. 3) 标签: combinatorics, math 难度: *1400

喵喵，题目在说什么呀？

你好呀，我是乐于助人的猫娘~ 这道题目其实很可爱哦！

想象一下，我们有一辆神奇的巴士，它有一个最大载客量 w，也就是说，车上的人数必须时刻保持在 0 到 w 之间（包括0和w哦）。

这辆巴士经过了 n 个站台，它的监控系统没有记录每个站台之后车上具体有多少人，而是记录了人数的 变化量 a_i。比如 a_1 = 2 就表示第一个站台之后，车上的人多了2个；a_3 = -3 就表示第三个站台之后，少了3个人。

我们的任务就是，根据这一系列的乘客变化量 a_1, a_2, ..., a_n，来计算出在发车前（也就是在第一个站台之前），车上可能有多少名乘客呢？我们要找出所有可能的初始乘客数量，然后告诉总共有多少种可能性，的说。如果无论初始有多少人，中途都会违反 0 <= 乘客数 <= w 这个规则，那答案就是0啦。

解题思路大揭秘喵！

这道题的核心，就是找到一个初始乘客数 c_0 的取值范围，喵~

让我们来一步步分析吧！

设定未知数: 设巴士在发车前的初始乘客数量为 c_0。这是我们要寻找的变量。
核心约束: 无论在哪个时刻，巴士上的乘客数量 p 都必须满足 0 <= p <= w。这个约束条件贯穿始终！
追踪乘客数量:
- 在发车前，乘客数是 c_0。
- 经过第1个站台后，乘客数变为 c_0 + a_1。
- 经过第2个站台后，乘客数变为 c_0 + a_1 + a_2。
- ...
- 经过第 k 个站台后，乘客数变为 c_0 + (a_1 + a_2 + ... + a_k)。
我们可以发现，在第 k 个站台后的乘客数，等于初始人数 c_0 加上前 k 个站台的变化量之和。这个“变化量之和”就是前缀和呀！让我们定义 S_k = a_1 + a_2 + ... + a_k。那么第 k 站后的乘客数就是 c_0 + S_k。
建立不等式: 现在，我们把核心约束应用到每个时刻：
- 发车前：0 <= c_0 <= w
- 对任意一个站台 k (从 1 到 n)：0 <= c_0 + S_k <= w
我们把第二个不等式稍微变形，把 c_0 单独放在中间： -S_k <= c_0 <= w - S_k
合并所有约束: c_0 必须同时满足所有这些不等式！这意味着 c_0 必须大于等于所有下界中的最大值，并且小于等于所有上界中的最小值。
- 下界 (Lower Bound): c_0 必须大于等于 0，也要大于等于所有的 -S_k。所以，c_0 的下界是 max(0, -S_1, -S_2, ..., -S_n)。
- 上界 (Upper Bound): c_0 必须小于等于 w，也要小于等于所有的 w - S_k。所以，c_0 的上界是 min(w, w - S_1, w - S_2, ..., w - S_n)。
寻找最值: 让我们来简化一下这个过程。我们可以遍历整个旅程，记录下前缀和 S_k 在整个过程中的最小值 min_prefix 和最大值 max_prefix。（注意哦，旅程开始前的前缀和是0，所以 min_prefix 的初值是0，max_prefix 的初值也是0）。
- 为了保证乘客数永远不会小于0，即使在乘客数最少的时候（也就是前缀和达到 min_prefix 的时候），也要满足 c_0 + min_prefix >= 0。所以 c_0 >= -min_prefix。这就是我们最终的下界 L。
- 为了保证乘客数永远不会超过 w，即使在乘客数最多的时候（也就是前缀和达到 max_prefix 的时候），也要满足 c_0 + max_prefix <= w。所以 c_0 <= w - max_prefix。这就是我们最终的上界 U。
计算结果: 我们找到了 c_0 的合法取值范围是 [L, U]，也就是 [-min_prefix, w - max_prefix]。那么，这个区间里有多少个整数呢？当然是 U - L + 1 啦！
不过要小心一个特殊情况：如果算出来 L > U，说明下界比上界还大，这意味着不存在任何一个合法的 c_0。这时候，可能的方案数就是 0 啦，喵~

总结一下我们的算法：

初始化当前前缀和 current = 0，最小前缀和 min_prefix = 0，最大前缀和 max_prefix = 0。
遍历所有 n 个变化量 a_i：
- 更新 current += a_i。
- 更新 min_prefix = min(min_prefix, current)。
- 更新 max_prefix = max(max_prefix, current)。
计算最终的下界 L = -min_prefix 和上界 U = w - max_prefix。
如果 L > U，答案是 0。
否则，答案是 U - L + 1。

是不是很简单明了呢？呐，下面就来看看代码实现吧！

代码魔法时间~

cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long n, w;
    cin >> n >> w;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // current 用来记录当前的前缀和
    long long current = 0;
    // min_prefix 记录旅途中前缀和的最小值
    // max_prefix 记录旅途中前缀和的最大值
    // 初始时，前缀和为0，所以它们都初始化为0
    long long min_prefix = 0;
    long long max_prefix = 0;

    // 遍历所有站台的变化量
    for (int i = 0; i < n; i++) {
        // 更新当前的前缀和
        current += a[i];
        // 看看是否需要更新最小值
        if (current < min_prefix) {
            min_prefix = current;
        }
        // 看看是否需要更新最大值
        if (current > max_prefix) {
            max_prefix = current;
        }
    }

    // 根据推导，计算初始乘客数 c0 的下界 L
    // 为了保证 c0 + min_prefix >= 0，必须有 c0 >= -min_prefix
    long long L = -min_prefix;
    // 计算初始乘客数 c0 的上界 U
    // 为了保证 c0 + max_prefix <= w，必须有 c0 <= w - max_prefix
    long long U = w - max_prefix;

    // 如果下界比上界还大，说明没有合法的初始值
    if (L > U) {
        cout << 0 << endl;
    } else {
        // 否则，[L, U] 区间内的整数个数就是 U - L + 1
        cout << U - L + 1 << endl;
    }

    return 0;
}

效率分析喵

时间复杂度: 我们只需要对输入的 n 个变化量进行一次遍历，所以时间复杂度是 O(n) 的说。对于 n 最大为1000的情况，这简直是小菜一碟！
空间复杂度: 我们用一个 vector 存储了 n 个变化量，所以空间复杂度是 O(n) 的说。当然，也可以优化到 O(1)，边读入边处理，不把所有 a_i 存起来，但目前的写法已经足够通过啦。

猫娘的小课堂！

这道题虽然标签里有组合数学，但核心其实是前缀和与区间分析思想的巧妙运用，喵~

前缀和思想: 遇到“累积变化”、“区间和”这类问题，要立刻想到前缀和！它能帮我们快速得到任意一个时间点的状态相对于初始状态的变化量。
约束转换: 解题的关键一步是将对所有时刻的约束 0 <= c_0 + S_k <= w，统一转换为对初始值 c_0 的约束 -S_k <= c_0 <= w - S_k。这样问题就从动态追踪变成了求解一个静态的取值范围。
最值确定边界: 当一个变量需要满足一系列的 x >= L_i 和 x <= U_i 时，它的最终范围就是 [max(L_i), min(U_i)]。在本题中，我们通过追踪前缀和的全局最值 min_prefix 和 max_prefix，直接找到了最紧的那个边界条件。
边界处理: 不要忘记检查计算出的范围是否有效（即 L <= U）。如果无效，说明无解，答案为0。这是很多题目中容易忽略的细节哦！

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！一起加油，攻克更多有趣的题目吧，喵~

E. Bus Video System - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

解题思路大揭秘喵！ ​

代码魔法时间~ ​

效率分析喵 ​

猫娘的小课堂！ ​