这是使用 STL 标准库排序算法 std::sort 的版本。（使用了标准库的sort，代码少，但时间复杂度不是最优）

复杂度分析

• 时间复杂度：$O(N \log N)$。
  • 计算平方是 $O(N)$。
  • std::sort 的底层通常是快速排序（Quick Sort）或内省排序（Introsort），平均复杂度为 $O(N \log N)$。
• 能否 AC？：能！
  • 数据范围 $N=10^5$。
  • $N \log N \approx 10^5 \times 17 \approx 1.7 \times 10^6$ 次运算。
  • 这远小于 1 秒（$10^8$ 次）的限制。
• 评价：这是比赛中最稳妥、最快编写出来的解法（暴力优化版）。虽然不如双指针的 $O(N)$ 优雅，但在时间限制宽裕的情况下，它是完全可以接受的。

参考代码 (C++14)

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

// 【常规解法】
// 策略：先全部平方，再整体排序。
// 复杂度：O(N log N)

int main() {
    // 1. 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];
            // 直接原地修改：存入平方值
            // 无论正负，平方后都是非负数
            nums[i] = nums[i] * nums[i];
        }

        // 2. 调用标准库排序
        // 这一步的时间复杂度是 O(N log N)
        sort(nums.begin(), nums.end());

        // 3. 输出结果
        for (int i = 0; i < n; ++i) {
            cout << nums[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

教练点评

虽然这个代码能 AC，但请记住：

1. 面试中：面试官如果考这道题，通常是想看你是否会 $O(N)$ 的双指针解法。如果你只写这个，可能只能拿个及格分。
2. 极端情况下：如果题目 $N$ 增加到 $10^7$，这个解法可能会超时，而双指针依然能跑。

所以，这个解法是保底，双指针是满分。

给一个TLE版本的错误解答

为了让你深刻体会算法复杂度的重要性，我写了一个保证会 TLE (Time Limit Exceeded) 的版本。

为什么会 TLE？

• 正确解法（双指针）：$O(N)$。对于 $N=10^5$，大约计算 $10^5$ 次，耗时约 1ms。
• 普通解法（std::sort）：$O(N \log N)$。计算约 $1.7 \times 10^6$ 次，耗时约 30~50ms（其实能过，但不是最优）。
• 错误解法（冒泡排序）：$O(N^2)$。计算约 $10^{10}$ 次（100亿次）。
  • 现代评测机通常每秒处理 $10^8$ 次运算。
  • $10^{10} / 10^8 = 100$ 秒。
  • 题目限制通常是 1秒，所以这绝对会 TLE。

TLE 代码示例 (冒泡排序版)

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

// 【错误示范】
// 使用了 O(N^2) 的冒泡排序
// 当 N = 100,000 时，运算量高达 100亿次，绝对超时。

int main() {
    // 1. 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];
            // 直接原地平方
            nums[i] = nums[i] * nums[i];
        }

        // 2. 暴力排序：冒泡排序 (Bubble Sort)
        // 时间复杂度：O(N^2)
        for (int i = 0; i < n - 1; ++i) {
            for (int j = 0; j < n - 1 - i; ++j) {
                if (nums[j] > nums[j + 1]) {
                    // 交换
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }

        // 3. 输出
        for (int i = 0; i < n; ++i) {
            cout << nums[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

教学建议

你可以把这段代码提交到 OJ 上，观察结果。

• 对于测试点 1~5（$N$ 较小，比如几百），它能 AC。
• 对于测试点 7~10（$N=100,000$），它会运行很久然后被系统判 Time Limit Exceeded。

这就是为什么在 $N=10^5$ 的数据规模下，我们严禁使用 $O(N^2)$ 算法的原因。

这是一个完整的 C++ 数据生成器，专门用于生成“能量石的强度排序（Squares of a Sorted Array）”题目的测试数据。

它包含了标准解答（绝对正确的暴力排序法）和10种不同特征的数据生成逻辑，涵盖了正数、负数、零、大规模数据以及边界情况。

Generator 代码 (gen_squares.cpp)

请将以下代码保存为 gen_squares.cpp，编译并运行即可在当前目录下生成 1.in/1.out 到 10.in/10.out。

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

// ==========================================
// Part 1: 标准解答 (Standard Solution)
// 用于生成绝对正确的 .out 文件
// 为了保证 Generator 的正确性，这里直接使用 sort，
// 虽然时间复杂度是 O(NlogN)，但作为生成器在本地运行完全没问题，且逻辑最不容易出错。
// ==========================================
vector<int> solve(vector<int> nums) {
    int n = nums.size();
    vector<int> res(n);
    for(int i=0; i<n; i++) {
        res[i] = nums[i] * nums[i];
    }
    // 直接排序，确保答案正确
    sort(res.begin(), res.end());
    return res;
}

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

int random_int(int L, int R) {
    return uniform_int_distribution<int>(L, R)(rng);
}

// 生成指定模式的数据
void generate_case(int case_id) {
    int n;
    vector<int> a;

    // 数据范围定义
    const int MAX_VAL = 10000;
    
    switch (case_id) {
        case 1: // 【样例 1】
            n = 5;
            a = {-4, -1, 0, 3, 10};
            break;
            
        case 2: // 【样例 2】
            n = 5;
            a = {-7, -3, 2, 3, 11};
            break;
            
        case 3: // 【纯正数】从小到大
            n = 100;
            for(int i=0; i<n; i++) a.push_back(random_int(0, 1000));
            break;
            
        case 4: // 【纯负数】从小到大 (实际上是绝对值从大到小)
            n = 100;
            for(int i=0; i<n; i++) a.push_back(random_int(-1000, -1));
            break;
            
        case 5: // 【全零】边界情况
            n = 20;
            for(int i=0; i<n; i++) a.push_back(0);
            break;
            
        case 6: // 【混合】正负交织
            n = 200;
            for(int i=0; i<n; i++) a.push_back(random_int(-1000, 1000));
            break;
            
        case 7: // 【大规模】随机混合，满数据范围
            n = 100000;
            for(int i=0; i<n; i++) a.push_back(random_int(-MAX_VAL, MAX_VAL));
            break;
            
        case 8: // 【大规模】纯正数 (测试如果不移动指针的性能)
            n = 100000;
            for(int i=0; i<n; i++) a.push_back(random_int(0, MAX_VAL));
            break;
            
        case 9: // 【大规模】纯负数 (测试反向填充逻辑)
            n = 100000;
            for(int i=0; i<n; i++) a.push_back(random_int(-MAX_VAL, 0));
            break;
            
        case 10: // 【极端】只有极大值和极小值
            n = 100000;
            for(int i=0; i<n; i++) {
                // 随机生成接近 -10000 或 10000 的数
                if (random_int(0, 1)) a.push_back(random_int(9900, 10000));
                else a.push_back(random_int(-10000, -9900));
            }
            break;
            
        default:
            n = 10;
            for(int i=0; i<n; i++) a.push_back(i);
    }

    // !!! 关键步骤 !!!
    // 题目输入要求数组必须是【非递减】的
    // 除了 Case 1 和 2 是手动写好的，其他随机生成的必须先 Sort 一遍才能写入 .in
    if (case_id > 2) {
        sort(a.begin(), a.end());
    }

    // ==========================================
    // 文件输出
    // ==========================================
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    cout << "Generating Case " << case_id << " (N=" << n << ")..." << endl;

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

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

int main() {
    // 循环生成 1 到 10 号测试点
    for (int i = 1; i <= 10; ++i) {
        generate_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

使用指南

1. 编译：

   g++ gen_squares.cpp -o gen -std=c++14 -O2
   

2. 运行：

   ./gen  # Windows: gen.exe
   

3. 结果检查：
   • 1.in: 应该看到样例数据 5 和 -4 -1 0 3 10。
   • 4.in (纯负数): 输入应该是 -1000 ... -1 这样的顺序（必须是升序）。
   • 4.out: 输出应该是 1 ... 1000000 这样的顺序（也是升序）。
   • 7.in (大规模): 打开文件确认 $N=100000$，且数字是从负到正有序排列的。

这套数据生成器确保了输入文件严格遵守题目要求的“非递减顺序”，并且覆盖了 $O(N)$ 双指针解法可能遇到的各种边界情况。

【参考代码 (C++14 OI Style)】

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

// 题目：有序数组的平方
// 核心思想：利用双指针，从两头向中间逼近，逆序填充结果数组

int main() {
    // 1. 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> res(n);
        
        // 2. 双指针初始化
        int left = 0;
        int right = n - 1;
        
        // pos 指向结果数组的末尾（因为我们要从大到小填）
        int pos = n - 1;

        // 3. 开始对决：左右互搏
        while (left <= right) {
            // 计算两端的平方值
            // 注意：不用真的算平方，直接比绝对值也可以，但算平方更直观，且题目没说会溢出
            int val1 = nums[left] * nums[left];
            int val2 = nums[right] * nums[right];

            if (val1 > val2) {
                // 左边的平方更大
                res[pos] = val1;
                left++; // 左指针右移
            } else {
                // 右边的平方更大（或相等）
                res[pos] = val2;
                right--; // 右指针左移
            }
            pos--; // 结果数组填好了一位，前移
        }

        // 4. 输出结果
        for (int i = 0; i < n; ++i) {
            cout << res[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

【自我检查】

1. 循环条件：为什么是 while (left <= right) 而不是 <？
   • 因为当 left == right 时，还剩最后一个元素（通常是最小的那个），我们也需要把它填入结果数组中。
2. 填充顺序：为什么要从 pos = n-1 开始填？
   • 因为双指针找到的是“最大值”，如果从 0 开始填，你需要把它们反转或者用复杂的逻辑找最小值。逆序填充是最顺手的。