题解：Rainy Markets

题目分析

问题核心

给定 (N) 个公交车站、(N-1) 个中间市场，每个市场的人需选择前往左侧车站、右侧车站或购买雨伞（每人限1把）。需判断是否能让所有人都不淋湿，并在可行时给出最少雨伞花费（即买伞人数最少）的方案。

关键约束

1. 每个市场 (i) 的人数分配需满足：(a_i + b_i + c_i = P_i)（(a_i) 去车站 (i)，(b_i) 买伞，(c_i) 去车站 (i+1)）。
2. 车站容量限制：所有前往车站 (k) 的人数总和 ≤ (B_k)（前往车站 (k) 的人来自市场 (k-1) 的 (c_{k-1}) 和市场 (k) 的 (a_k)）。
3. 买伞限制：(0 ≤ b_i ≤ U_i)（(U_i) 为市场 (i) 的雨伞数量）。
4. 优化目标：最小化总买伞人数 (\sum b_i)（因每把伞价格为1，总花费即总买伞人数）。

数据范围挑战

• (N ≤ 10^6)，需 (O(N)) 时间复杂度算法，不能使用动态规划等复杂状态转移。
• 数值范围极大（(B_i, P_i, U_i ≤ 10^9)），需避免溢出，使用64位整数存储结果。

算法设计

核心思路

要使买伞人数最少，需优先让市场的人前往两侧车站，仅当车站容量不足时才选择买伞。由于车站 (k) 的容量被市场 (k-1) 的右侧流出（(c_{k-1})）和市场 (k) 的左侧流入（(a_k)）共同占用，需分两步预处理：

1. 正向预处理：计算每个市场 (i) 左侧车站 (i) 可接纳的最大人数（排除前一个市场的右侧流出占用）。
2. 反向分配：从最右侧市场开始，优先分配人员到右侧车站，再分配到左侧车站，最后用买伞填补剩余人数，确保车站容量不超限。

具体步骤

1. 正向预处理：计算左侧车站可用容量 (dp[i])

定义 (dp[i]) 为市场 (i) 对应的左侧车站 (i) 可接纳的最大人数（已扣除市场 (i-1) 流入的 (c_{i-1}) 占用）。

• 对于市场 (i)，车站 (i) 的总容量为 (B[i])。
• 市场 (i-1) 流向车站 (i) 的人数为 (c_{i-1})，而 (c_{i-1} = P_{i-1} - a_{i-1} - b_{i-1})。由于优先减少买伞，(b_{i-1}) 最小为0，因此 (c_{i-1}) 最大为 (P_{i-1} - a_{i-1})。
• 为保证车站 (i) 有足够容量接纳 (c_{i-1})，需预留 (max(P_{i-1} - dp[i-1], 0)) 个容量（(dp[i-1]) 是市场 (i-1) 左侧车站的最大接纳数，即 (a_{i-1}) 的最大值）。
• 因此：(dp[i] = max(B[i] - max(P_{i-1} - dp[i-1], 0), 0))（若结果为负，取0表示无可用容量）。

2. 反向分配：确定 (a_i, b_i, c_i)

从最右侧市场 (N-1) 向左遍历，按以下优先级分配人员：

• 优先级1：分配到右侧车站 (i+1)（(c_i)）：右侧车站 (i+1) 的剩余容量为 (B[i+1] - a_{i+1})（(a_{i+1}) 是市场 (i+1) 分配到左侧车站的人数），因此 (c_i = min(P[i], B[i+1] - a_{i+1}))。
• 优先级2：分配到左侧车站 (i)（(a_i)）：左侧车站 (i) 的可用容量为 (dp[i])，因此 (a_i = min(P[i] - c_i, dp[i]))。
• 优先级3：买伞 (b_i)：剩余未分配的人数用买伞填补，(b_i = min(P[i] - c_i - a_i, U[i]))。
• 剩余人数处理：若买伞后仍有剩余，说明需增加左侧车站的接纳人数（因买伞已达上限），此时 (a_i +=) 剩余人数，最终需检查 (a_i) 是否超过车站 (i) 的总容量 (B[i])（若超过则无解）。

无解判断

• 反向分配过程中，若某市场 (i) 最终 (a_i > B[i])（左侧车站容量超限），或 (b_i > U[i])（雨伞不足），则输出 NO。
• 总可容纳人数（(\sum B[i] + \sum U[i])）< 总人数（(\sum P[i])）时，直接输出 NO（代码中通过反向分配自然判断，无需提前计算总和，避免溢出）。

代码关键模块解析

1. 快速读写模块

由于 (N) 达 (10^6)，需使用缓冲区读写优化速度：

// 快速读入
inline char nc() { /* 从缓冲区读取字符 */ }
inline int read() { /* 读取整数 */ }
// 快速写出
inline void pc(char x) { /* 写入字符到缓冲区 */ }
template <typename T> inline void write(T x) { /* 写入整数 */ }

2. 正向预处理 (dp) 数组

for (int i = 1; i < n; i++)
    u[i] = read(), dp[i] = std::max(b[i] - std::max(p[i - 1] - dp[i - 1], 0), 0);

• (dp[1]) 特殊处理：(i=1) 时无市场 (0)，因此 (max(P[0] - dp[0], 0) = 0)，(dp[1] = min(B[1], P[1]))（代码中自然体现）。

3. 反向分配核心逻辑

for (int i = n - 1; i >= 1; i--) {
    // 优先级1：分配到右侧车站i+1
    p3[i] = std::min(p[i], b[i + 1] - p1[i + 1]);
    p[i] -= p3[i];
    // 优先级2：分配到左侧车站i
    p1[i] = std::min(p[i], dp[i]);
    p[i] -= p1[i];
    // 优先级3：买伞
    p2[i] = std::min(p[i], u[i]);
    p[i] -= p2[i];
    // 剩余人数补充到左侧车站（买伞已用尽）
    p1[i] += p[i];
    // 检查左侧车站容量是否超限
    if (p1[i] > b[i]) {
        pc('N'), pc('O');
        fwrite(obuf, P3 - obuf, 1, stdout);
        return 0;
    }
    ans += (ll)(p2[i]); // 累计买伞人数（总花费）
}

• (p1[i] = a_i)（去左侧车站人数），(p2[i] = b_i)（买伞人数），(p3[i] = c_i)（去右侧车站人数）。
• 最终检查 (p1[i] > b[i])，若成立则左侧车站容量不足，输出 NO。

4. 结果输出

pc('Y'), pc('E'), pc('S'), pc('\n');
write(ans), pc('\n');
for (int i = 1; i < n; i++)
    write(p1[i]), pc(' '), write(p2[i]), pc(' '), write(p3[i]), pc('\n');

• 输出 YES、总买伞花费，以及每个市场的人数分配方案。

时间复杂度与空间复杂度

• 时间复杂度：(O(N))，正向预处理和反向分配各遍历一次数组，读写操作均为线性时间。
• 空间复杂度：(O(N))，存储输入数组 (B, P, U) 和分配结果数组 (p1, p2, p3)、预处理数组 (dp)，符合 (N ≤ 10^6) 的空间限制。

关键结论

1. 最小买伞人数的核心是“优先车站，后买伞”，通过正向预处理车站可用容量、反向分配人员，确保车站容量不冲突。
2. 反向分配从右侧开始，可直接利用后续市场的分配结果（(a_{i+1})）计算当前市场的右侧流出容量（(c_i)），避免二次遍历。
3. 数值溢出处理：总买伞人数用 long long 存储，所有中间计算避免负数（用 max(..., 0) 截断）。