你好！作为一名经验丰富的OI教练，我为你准备了一个功能完备的数据生成器。

这个生成器不仅集成了标准题解代码（用于生成正确的 .out 文件），还精心设计了 10 个测试点，覆盖了从极小数据、单调数据、全零数据到大数据压力测试等各种场景，确保你的测试数据具有极高的质量。

数据生成器设计思路

1. 集成标程：内置了 $O(n)$ 的双指针解法，保证输出答案绝对正确。
2. 覆盖全面：
   • 边界情况：$N=1$（最小）、全为 0、全正、全负。
   • 一般情况：正负交替、随机分布。
   • 压力测试：$N=10000$ 的大数据，覆盖满值域。
3. 合法性保证：题目要求输入数组是有序的，所以生成器在生成随机数后，会先执行一次 sort 再写入 .in 文件。

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

请将以下代码保存为 gen.cpp，编译运行后，当前目录下会自动生成 1.in ~ 10.in 和 1.out ~ 10.out。

/**
 * NOI/CSP 竞赛题目数据生成器
 * 题目：有序数组的平方
 * 功能：自动生成 1.in/out 到 10.in/out 测试数据
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <random>
#include <chrono>

using namespace std;

// ==========================================
// Part 1: 标准题解代码 (用于生成 .out 文件)
// ==========================================
vector<int> solve(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n);
    int left = 0;
    int right = n - 1;
    int pos = n - 1;

    while (left <= right) {
        int sqLeft = nums[left] * nums[left];
        int sqRight = nums[right] * nums[right];
        if (sqLeft > sqRight) {
            result[pos] = sqLeft;
            left++;
        } else {
            result[pos] = sqRight;
            right--;
        }
        pos--;
    }
    return result;
}

// ==========================================
// Part 2: 随机数生成工具
// ==========================================
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

// ==========================================
// Part 3: 数据生成逻辑
// ==========================================
void generateData(int caseNum, int n, int minVal, int maxVal, const string& type = "random") {
    // 构造文件名
    string inFile = to_string(caseNum) + ".in";
    string outFile = to_string(caseNum) + ".out";

    // 1. 生成数据
    vector<int> nums(n);
    
    if (type == "random") {
        for (int i = 0; i < n; ++i) {
            nums[i] = randomInt(minVal, maxVal);
        }
    } 
    else if (type == "zero") {
        // 特殊情况：全0
        fill(nums.begin(), nums.end(), 0);
    } 
    else if (type == "extreme_gap") {
        // 特殊情况：两头密集，中间空缺（模拟大绝对值）
        for (int i = 0; i < n; ++i) {
            if (randomInt(0, 1) == 0) nums[i] = randomInt(minVal, minVal + 1000);
            else nums[i] = randomInt(maxVal - 1000, maxVal);
        }
    }

    // 2. 关键步骤：题目要求输入必须是有序的
    sort(nums.begin(), nums.end());

    // 3. 写入 .in 文件
    ofstream fin(inFile);
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << nums[i] << (i == n - 1 ? "" : " ");
    }
    fin << "\n";
    fin.close();

    // 4. 计算答案并写入 .out 文件
    vector<int> ans = solve(nums);
    ofstream fout(outFile);
    for (int i = 0; i < n; ++i) {
        fout << ans[i] << (i == n - 1 ? "" : " ");
    }
    fout << "\n";
    fout.close();

    cout << "Generated Case " << caseNum << ": N=" << n << " Range=[" << minVal << ", " << maxVal << "]" << endl;
}

int main() {
    // 数据范围限制
    const int MAX_VAL = 10000;
    const int MIN_VAL = -10000;
    const int N_SMALL = 10;
    const int N_MEDIUM = 100;
    const int N_LARGE = 10000; // 题目最大 N

    // --- 测试点配置 ---
    
    // Test 1: 极小数据 (N=1)
    generateData(1, 1, -100, 100);

    // Test 2: 小数据，全正数 (单调递增测试)
    generateData(2, N_SMALL, 1, 100);

    // Test 3: 小数据，全负数 (单调递减测试，平方后反转)
    generateData(3, N_SMALL, -100, -1);

    // Test 4: 中等数据，跨越0点，一般情况
    generateData(4, N_MEDIUM, -100, 100);

    // Test 5: 边界情况，全为0
    generateData(5, N_MEDIUM, 0, 0, "zero");

    // Test 6: 大数据，随机分布 (标准压力测试)
    generateData(6, N_LARGE, MIN_VAL, MAX_VAL);

    // Test 7: 大数据，主要为负数 (偏态分布)
    generateData(7, N_LARGE, MIN_VAL, 500);

    // Test 8: 大数据，主要为正数 (偏态分布)
    generateData(8, N_LARGE, -500, MAX_VAL);

    // Test 9: 大数据，两极分化 (测试大数值计算)
    // 这种数据生成的平方数都很大，容易测试溢出问题（虽然本题int够用）
    generateData(9, N_LARGE, MIN_VAL, MAX_VAL, "extreme_gap");

    // Test 10: 大数据，密集数据 (范围小，重复元素多)
    generateData(10, N_LARGE, -10, 10);

    cout << "All 10 test cases generated successfully!" << endl;
    return 0;
}

测试点详细说明表

如何使用

1. 确保你的电脑上安装了 C++ 编译器（如 g++）。
2. 将上述代码保存为 data_gen.cpp。
3. 编译：g++ data_gen.cpp -o data_gen -std=c++14
4. 运行：./data_gen (Windows 下是 data_gen.exe)
5. 你的目录下会出现 1.in~10.in 和 1.out~10.out 共 20 个文件，可以直接上传到 OJ 系统。

你好！我是你的OI金牌教练。

既然你已经思考了双指针的策略，现在我给出符合 NOIP/CSP 竞赛标准 的 C++14 题解代码。这份代码展示了在赛场上如何写出稳健、高效且易于调试的程序。

标准题解代码 (C++14)

/**
 * 题目名称：有序数组的平方 (Squares of a Sorted Array)
 * 算法标签：双指针 (Two Pointers)、数组操作
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */

#include <iostream>
#include <vector>
#include <algorithm>

// 使用 std 命名空间，在竞赛代码中很常见，可以减少代码量
using namespace std;

// 核心逻辑封装在函数中，保持 main 函数简洁
// 使用 const reference 避免数组拷贝，提高效率
vector<int> sortedSquares(const vector<int>& nums) {
    int n = nums.size();
    
    // 易错点1: 必须预先分配空间，否则直接使用索引 result[k] 会越界
    // 也可以用 result.push_back() 但那样需要最后 reverse，不如直接指定大小效率高
    vector<int> result(n);
    
    // 定义双指针
    int left = 0;           // 指向原数组最左端（可能包含绝对值最大的负数）
    int right = n - 1;      // 指向原数组最右端（可能包含绝对值最大的正数）
    int pos = n - 1;        // 结果数组的填充指针，从后往前填（因为我们要找最大的）

    // 关键点: 循环条件必须包含 left == right
    // 否则当只剩最后一个元素时，该元素会被遗漏
    while (left <= right) {
        // 计算平方值
        // 数据范围提示: -10^4 <= A[i] <= 10^4
        // 平方最大为 10^8，int 类型 (约2*10^9) 足够存储，无需 long long
        int sqLeft = nums[left] * nums[left];
        int sqRight = nums[right] * nums[right];

        // 贪心策略：谁的平方大，谁就放到当前结果数组的最后面
        if (sqLeft > sqRight) {
            result[pos] = sqLeft;
            left++;     // 左边元素已处理，左指针右移
        } else {
            result[pos] = sqRight;
            right--;    // 右边元素已处理，右指针左移
        }
        
        pos--; // 填充位置向前移动
    }

    return result;
}

int main() {
    // 竞赛必备优化：关闭 C++ 标准流与 C 标准流的同步，加快 cin/cout 速度
    // 在数据量达到 10^5 或 10^6 级别时，此操作能防止 I/O 超时
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) {
            cin >> nums[i];
        }

        // 调用算法
        vector<int> ans = sortedSquares(nums);

        // 输出结果，注意行末空格的处理符合常见 OJ 格式
        for (int i = 0; i < n; ++i) {
            cout << ans[i] << (i == n - 1 ? "" : " ");
        }
        cout << endl; // 行末换行
    }

    return 0;
}

复杂度分析与思考过程

1. 时间复杂度分析

• 思考过程：
  • 如果我们使用“先平方后排序”的暴力法，平方操作是 $O(n)$，快速排序是 $O(n \log n)$，总复杂度由排序决定，为 $O(n \log n)$。
  • 观察到原数组已经是有序的（虽然负数破坏了平方后的单调性，但它呈现“V”字形或“U”字形），我们利用双指针策略。
  • 在 while 循环中，left 指针只能向右移动，right 指针只能向左移动。
  • 每次循环，要么 left 加 1，要么 right 减 1，总共的操作次数正好是数组长度 $n$。
• 结论：$O(n)$。
• 优化建议：对于本题，$O(n)$ 已经是理论下界（至少需要遍历一次数组），无法在算法层级进一步优化。代码层面的微小优化包括使用 result(n) 预分配内存而不是 push_back，避免动态扩容的开销。

2. 空间复杂度分析

• 思考过程：
  • 我们需要一个和原数组等长的数组 result 来存储排序后的平方数。
  • 除此之外，只使用了 left, right, pos, sqLeft, sqRight 等常数个变量。
• 结论：$O(n)$（用于存储输出结果）。
  • 注意：如果在某些严格定义下，输出空间不计入复杂度，则额外空间复杂度为 $O(1)$。但在竞赛中通常认为开辟了新数组就是 $O(n)$。

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

1. 循环终止条件：

   • 易错点：写成 while (left < right)。
   • 后果：当 left 和 right 相遇时（指向同一个元素，也就是最后一个剩下的最小平方数），循环终止，导致这个元素没有被写入结果数组。
   • 修正：必须是 while (left <= right)。

2. 结果填充方向：

   • 关键点：一定要从 n-1（后）往前填充。
   • 原因：原数组两端（极大正数或极小负数）的平方一定是最大的，只有确定了“最大”的，才能确定位置（放在最后）。如果试图找“最小”的，由于最小值在数组中间某处，难以直接定位。

3. 数据溢出 (Overflow)：

   • 检查：题目给出的范围是 $|A_i| \le 10^4$。
   • 计算：$(10^4)^2 = 10^8$。
   • 判断：int 的最大值通常是 $2 \times 10^9$ (即 2147483647)。$10^8 < 2 \times 10^9$，所以使用 int 是安全的。如果题目范围改到 $10^5$，则平方为 $10^{10}$，必须使用 long long。

4. I/O 效率：

   • 在 NOIP/CSP 复赛中，如果不写 ios::sync_with_stdio(false);，在大数据量（如 $n=10^6$）的题目中可能会因为 I/O 慢而 TLE（超时）。这是考场上的标准动作。

希望这份标准代码和分析能成为你解题的模范！继续加油！