DP解法

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    
    // DP: leftMax[i] = 位置i左边（含i）的最大高度
    vector<int> leftMax(n);
    leftMax[0] = h[0];
    for (int i = 1; i < n; i++) {
      //关键点1： 前缀,[0,i]范围=[0,i-1]范围+h[i]差分量
        leftMax[i] = max(leftMax[i - 1], h[i]);
    }
    
    // DP: rightMax[i] = 位置i右边（含i）的最大高度
    vector<int> rightMax(n);
    rightMax[n - 1] = h[n - 1];
    for (int i = n - 2; i >= 0; i--) {
      //关键点2： 后缀，[i,n-1]范围=[i+1,n-1]范围+h[i]差分量
        rightMax[i] = max(rightMax[i + 1], h[i]);
    }
    
    // 计算总储水量
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        //关键点3：位置i的水平面
        int level = min(leftMax[i], rightMax[i]);
        //关键点4：如果水平面高于位置i的柱子高度，则储水=水平面高度-柱子高度
        ans += level - h[i];
    }
    
    cout << ans << endl;
    
    return 0;
}

这是一个为你定制的 NOI 风格数据生成器。它将自动生成 1.in ~ 10.in 和对应的 1.out ~ 10.out 文件。

这个生成器集成了之前的双指针标准解法来计算正确答案，确保数据和答案的绝对匹配。数据点覆盖了：极小值边界、单调递增/递减、山峰/山谷形状、随机大数据以及最大数据压力测试。

使用方法

1. 将下方代码保存为 generator.cpp。
2. 编译并运行：g++ generator.cpp -o generator -std=c++14 && ./generator (Linux/Mac) 或直接在 IDE 中运行。
3. 程序运行结束后，当前目录下会出现 10 组输入输出文件。

数据生成器代码 (C++14)

#include <iostream>
#include <vector>
#include <string>
#include <fstream>   // 用于文件读写
#include <algorithm> // 用于 max, min
#include <random>    // 用于生成随机数
#include <chrono>    // 用于随机数种子

using namespace std;

// ==========================================
// Part 1: 标准解法 (Solver)
// ==========================================
// 使用双指针法计算结果，复杂度 O(N)
long long solve_trapping_rain_water(int n, const vector<int>& height) {
    if (n < 3) return 0;

    int left = 0;
    int right = n - 1;
    int max_left = 0;
    int max_right = 0;
    long long ans = 0;

    while (left <= right) { // 注意：这里用 <= 处理最后相遇的情况，虽然 height[left]此时已被计算过或不存水，但逻辑通用
        if (max_left < max_right) {
            if (height[left] >= max_left) {
                max_left = height[left];
            } else {
                ans += (max_left - height[left]);
            }
            left++;
        } else {
            if (height[right] >= max_right) {
                max_right = height[right];
            } else {
                ans += (max_right - height[right]);
            }
            right--;
        }
    }
    return ans;
}

// ==========================================
// Part 2: 数据生成策略
// ==========================================

// 随机数生成器初始化
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// 生成 [min_val, max_val] 范围内的随机整数
int random_int(int min_val, int max_val) {
    uniform_int_distribution<int> dist(min_val, max_val);
    return dist(rng);
}

// 生成特定的测试点数据
void generate_case(int case_id, int& n, vector<int>& h) {
    h.clear();
    const int MAX_H = 100000;
    const int MAX_N = 20000;

    switch (case_id) {
    case 1: // 【边界情况】极小数据 N=0 (题目允许非负，需考虑 N=0 或 N=1)
        n = 0;
        // h 为空
        break;

    case 2: // 【边界情况】无法接水的情况 N=2
        n = 2;
        h = {MAX_H, MAX_H};
        break;

    case 3: // 【特殊构造】单调递增 (梯田)，接不到水
        n = 100;
        for (int i = 0; i < n; i++) h.push_back(i * 100);
        break;

    case 4: // 【特殊构造】单调递减，接不到水
        n = 100;
        for (int i = 0; i < n; i++) h.push_back((n - i) * 100);
        break;

    case 5: // 【特殊构造】凸型 (山峰 A字型)，中间高两边低，接不到水
        n = 1000;
        for (int i = 0; i < n / 2; i++) h.push_back(i * 10);
        for (int i = n / 2; i < n; i++) h.push_back((n - i) * 10);
        break;

    case 6: // 【特殊构造】凹型 (山谷 V字型)，两边极高中间低，接水最多
        n = 2000;
        h.push_back(MAX_H); // 左墙
        for (int i = 1; i < n - 1; i++) h.push_back(0); // 中间全是平地
        h.push_back(MAX_H); // 右墙
        break;

    case 7: // 【常规随机】中等规模 N=5000
        n = 5000;
        for (int i = 0; i < n; i++) h.push_back(random_int(0, 1000));
        break;

    case 8: // 【特殊构造】锯齿状 (高低交错)，测试频繁波动的逻辑
        n = 10000;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) h.push_back(random_int(8000, 10000)); // 高
            else h.push_back(random_int(0, 2000));      // 低
        }
        break;

    case 9: // 【压力测试】最大 N，全随机高度
        n = MAX_N;
        for (int i = 0; i < n; i++) h.push_back(random_int(0, MAX_H));
        break;

    case 10: // 【极端压力】最大 N，最大高度差，测试 long long 溢出风险
             // 两端极高，中间随机且偏低，模拟大坝
        n = MAX_N;
        h.push_back(MAX_H);
        for (int i = 1; i < n - 1; i++) h.push_back(random_int(0, MAX_H / 2));
        h.push_back(MAX_H);
        break;
    }
}

// ==========================================
// Part 3: 主程序
// ==========================================
int main() {
    printf("开始生成测试数据 (1.in ~ 10.in / 1.out ~ 10.out)...\n");

    for (int i = 1; i <= 10; i++) {
        string in_file = to_string(i) + ".in";
        string out_file = to_string(i) + ".out";

        // 1. 生成数据
        int n;
        vector<int> h;
        generate_case(i, n, h);

        // 2. 写入 .in 文件
        ofstream fin(in_file);
        fin << n << "\n";
        for (int k = 0; k < n; k++) {
            fin << h[k] << (k == n - 1 ? "" : " ");
        }
        fin << "\n"; // 文件末尾换行是好习惯
        fin.close();

        // 3. 计算答案
        long long ans = solve_trapping_rain_water(n, h);

        // 4. 写入 .out 文件
        ofstream fout(out_file);
        fout << ans << "\n";
        fout.close();

        printf("Case %d Generated: N = %d, Ans = %lld\n", i, n, ans);
    }

    printf("全部数据生成完毕。\n");
    return 0;
}

测试点设计说明 (1-10)

注意事项

1. 随机种子：代码使用了 chrono::steady_clock 初始化随机种子，确保每次运行生成的随机数据略有不同（如果想固定数据，可以将 rng 初始化时的参数改为固定整数）。但对于同一批生成的 .in 和 .out，它们是严格对应的。
2. 文件格式：输入数组之间用空格分隔，符合 NOI/OJ 通用格式。
3. 效率优化：生成器逻辑简单，且 $N$ 较小（2万），直接运行即可瞬间完成，无需额外的树/图生成优化。

作为金牌教练，我为你准备了这道题的NOIP/NOI 竞赛标准解法。

在信息学竞赛中，对于《接雨水》这道题，双指针法 (Two Pointers) 是最优解（时间 $O(N)$，空间 $O(1)$），也是高水平选手必须掌握的技巧。相比于动态规划法需要开额外的数组空间，双指针法在空间效率上做到了极致。

以下是符合 C++14 标准的代码，包含详细的注释和复杂度分析。

1. NOIP 标准参考代码 (C++14)

/*
 * 题目名称：接雨水 (Trapping Rain Water)
 * 算法核心：双指针 (Two Pointers) / 贪心
 * 考察点：线性扫描、空间优化、单调性利用
 * 
 * 对应 LeetCode 42
 * 编写风格：NOI/NOIP C++14 标准
 */

#include <iostream>
#include <vector>
#include <algorithm> // 用于 max, min
#include <cstdio>    // 用于 scanf, printf (在大数据量下比 cin 更稳健)

using namespace std;

// 定义最大数组大小，根据题目说明 N <= 20000
// 竞赛习惯：稍微开大一点，防止边界溢出
const int MAXN = 20005;

int n;
int height[MAXN];

int main() {
    // 【输入处理】
    // 使用 scanf 提高读入效率
    if (scanf("%d", &n) != 1) return 0;
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &height[i]);
    }

    // 【特殊情况处理】
    // 如果柱子少于3根，根本无法形成凹槽，直接输出0
    if (n < 3) {
        printf("0\n");
        return 0;
    }

    // 【核心逻辑：双指针法】
    int left = 0;           // 左指针
    int right = n - 1;      // 右指针
    
    int max_left = 0;       // 左边目前为止遇到的最高柱子
    int max_right = 0;      // 右边目前为止遇到的最高柱子
    
    // 易错点1：累加器建议使用 long long
    // 虽然题目数据范围可能不会爆 int，但在 NOI 赛场上，
    // 涉及累加求和的问题，使用 long long 是“零成本”的防溢出保险。
    long long ans = 0;

    // 当左右指针未相遇时循环
    while (left < right) {
        // 既然是从两边向中间缩，对于当前的 left 和 right：
        // height[left] 左边的最大值肯定是 max_left (正在维护)
        // height[right] 右边的最大值肯定是 max_right (正在维护)
        
        // 更新当前的左右边界最值
        // 这一步确保 max_left 是 height[0...left] 的最大值
        // max_right 是 height[right...n-1] 的最大值
        if (height[left] > max_left) max_left = height[left];
        if (height[right] > max_right) max_right = height[right];

        // 【核心思路：木桶效应】
        // 哪边的板子短，就处理哪边的数据。
        // 如果 max_left < max_right，说明对于 left 指针指向的位置：
        // 左边限制了它的水位上限（短板在左），而右边虽然可能有更高的墙，
        // 但根据木桶原理，水能不能存住、存多少，完全由较矮的 max_left 决定。
        // 至于 max_right 后面是不是还有更高的？不重要，反正右边已经有 max_right 兜底了。
        if (max_left < max_right) {
            // 计算当前 left 位置能接多少水
            // 公式：水位高度 - 柱子高度
            ans += max_left - height[left];
            left++; // 移动左指针
        } else {
            // 同理，如果 max_right <= max_left (短板在右)
            ans += max_right - height[right];
            right--; // 移动右指针
        }
    }

    // 【输出结果】
    printf("%lld\n", ans);

    return 0;
}

2. 复杂度分析与思考过程

在草稿纸上推导时，你应该遵循以下三个阶段的思考：

阶段一：暴力直觉 (Brute Force)

• 思考：对于数组中的每一个位置 $i$，它上面能存多少水？
• 逻辑：取决于它左边最高的墙和右边最高的墙中较矮的那个。$$\text{water}[i] = \min(\max(\text{left\_part}), \max(\text{right\_part})) - \text{height}[i] $$
• 代价：对每个 $i$ 都要向左向右扫描寻找最大值。
• 时间复杂度：$O(N^2)$。
• 评价：在 $N=20000$ 的情况下可能会超时，需优化。

阶段二：空间换时间 (Dynamic Programming)

• 优化：既然每次都要找左边最大和右边最大，为什么不把结果存起来？
• 逻辑：
  1. 开数组 L[N]，从左往右扫，L[i] 存 $0 \dots i$ 的最大值。
  2. 开数组 R[N]，从右往左扫，R[i] 存 $i \dots n-1$ 的最大值。
  3. 最后遍历一次计算答案。
• 时间复杂度：$O(N)$（扫三次）。
• 空间复杂度：$O(N)$（两个辅助数组）。
• 评价：可以通过，是标准的空间换时间策略。

阶段三：极致优化 (Two Pointers) —— 即上述代码解法

• 思考：我们真的需要知道右边确切的最高墙吗？如果我们只知道右边肯定有一个比左边高的墙，是不是就足够了？
• 逻辑：
  • 利用单调性。如果 max_left < max_right，那么对于 left 这个位置，右边必然存在一个（也就是当前的 max_right 或更远处的）墙比 max_left 高。
  • 因此，left 位置的水位完全由 max_left 决定。右边的具体情况不再是瓶颈。
  • 这样我们就可以省去存储数组的空间，直接一边遍历一边计算。
• 时间复杂度：$O(N)$（每个元素只访问一次）。
• 空间复杂度：$O(1)$（只用了几个变量）。
• 评价：NOI 金牌级解法，代码简练且效率最高。

3. 关键点与易错点总结（教练批注）

1. 数据类型安全：

   • ans 变量使用了 long long。虽然本题 $H \times N \approx 10^5 \times 2 \cdot 10^4 = 2 \cdot 10^9$，刚好卡在 int 边缘，但在竞赛中，凡是涉及“求和”、“体积”、“面积”的题目，无脑上 long long 是避免非智力失分的最好习惯。

2. 指针移动逻辑：

   • 很多同学容易在 if 判断里写错。记住口诀：“谁小移谁”（Who is smaller, moves）。
   • 因为短板决定容量，短的那一边一旦算完了当前位置的水，它的使命就暂时结束了，需要向中间探索看能不能找到更高的板子来提升水位。

3. 边界处理：

   • 代码中加入了 if (n < 3) 的判断。虽然在 $O(N)$ 逻辑下不加也能过（循环条件会自动拦截），但在正式比赛中显式处理边界情况体现了思维的严密性。

4. 输入输出：

   • 代码使用了 scanf/printf。对于 $N=20000$，cin/cout 也没问题，但如果题目扩展到 $N=10^6$，scanf 或关闭同步流的 cin 是必须的。保持这个习惯对未来打比赛很有好处。