这是一套完整的OI竞赛风格数据生成方案。为了创建一个高质量的评测集，我们需要编写一个“数据生成器（Generator）”和一个“标程（Solution）”。生成器负责制造符合题目约束的输入文件（.in），标程负责计算出对应的输出文件（.out）。

设计思路

1. 数据覆盖性：

   • 测试点 1-2：小规模数据（$N \le 10$），用于简单调试，涵盖正负数边界。
   • 测试点 3-5：中规模数据（$N \le 1000$），涵盖全部正数、全部负数、混合情况。
   • 测试点 6-8：大规模数据（$N = 30000$），随机分布，考察时间复杂度。
   • 测试点 9：大规模特定构造，解位于数组两端（考察双指针最坏移动距离）。
   • 测试点 10：大规模特定构造，解位于数组中间（考察双指针向中逼近）。

2. 难点处理（唯一解约束）：

   • 题目约束 $-1000 \le A[i] \le 1000$，但 $N$ 可达 $30000$。根据抽屉原理，大数组必然包含大量重复元素。
   • 虽然题目理论上要求“唯一解”，但在如此小的值域和大的 $N$ 下，构造严格唯一解极其困难。
   • 策略：我们在生成数据后，使用标准双指针算法来生成 .out。这样即使数据中存在多组解，只要选手的代码逻辑正确（符合双指针的查找顺序），就能输出与 .out 一致的结果（或者评测机开启 Special Judge 支持任意解，但在OI中通常我们让数据适应标程）。

3. 技术实现：

   • 使用 C++14 标准。
   • 使用 mt19937 高性能随机数引擎。
   • 自动批量生成 1.in ~ 10.in 和 1.out ~ 10.out。

数据生成器代码 (Generator)

请保存为 gen.cpp，编译并运行。它会在当前目录下生成 20 个文件。

/**
 * NOI Style Data Generator for "Two Sum II"
 * Language: C++14
 * 
 * 功能：自动生成 1.in ~ 10.in 及对应的 1.out ~ 10.out
 * 策略：覆盖小数据、大数据、全正、全负、解在两端、解在中间等情况
 */

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

using namespace std;

// --- 配置区域 ---
const int TOTAL_CASES = 10;
const int MAX_VAL = 1000;
const int MIN_VAL = -1000;

// --- 标程 (用于生成 .out) ---
// 必须与题目要求的正确解法完全一致
pair<int, int> solve(int n, long long target, const vector<int>& a) {
    int l = 0;
    int r = n - 1;
    while (l < r) {
        long long sum = (long long)a[l] + a[r];
        if (sum == target) {
            return {l + 1, r + 1}; // 返回 1-based 下标
        } else if (sum > target) {
            r--;
        } else {
            l++;
        }
    }
    return {-1, -1}; // 理论上不应该发生
}

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

int random_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

// --- 单个测试点生成逻辑 ---
void generate_case(int case_id) {
    // 1. 确定参数 N 和数据特性
    int n;
    int mode = 0; // 0:随机, 1:全正, 2:全负, 3:解在两端, 4:解在中间

    if (case_id <= 2) {
        n = random_int(2, 10); // 极小数据
    } else if (case_id <= 5) {
        n = random_int(100, 1000); // 中等数据
        if (case_id == 4) mode = 1; // 全正
        if (case_id == 5) mode = 2; // 全负
    } else {
        n = 30000; // 极限数据
        if (case_id == 8) mode = 3; // 解在两端
        if (case_id == 9) mode = 4; // 解在中间
        if (case_id == 10) n = 30000; // 综合压力测试
    }

    // 2. 生成有序数组
    vector<int> a(n);
    int current_min = MIN_VAL;
    int current_max = MAX_VAL;

    if (mode == 1) current_min = 1;       // 全正
    if (mode == 2) current_max = -1;      // 全负

    // 先随机生成
    for (int i = 0; i < n; ++i) {
        a[i] = random_int(current_min, current_max);
    }
    // 必须排序
    sort(a.begin(), a.end());

    // 3. 构造 Target 保证有解
    // 随机选取两个不同的下标作为"预设答案"
    int idx1, idx2;
    
    if (mode == 3) {
        // 强制解在极两端
        idx1 = 0;
        idx2 = n - 1;
    } else if (mode == 4) {
        // 强制解在中间附近
        idx1 = n / 2 - 1;
        idx2 = n / 2;
    } else {
        // 随机选择
        idx1 = random_int(0, n - 2);
        idx2 = random_int(idx1 + 1, n - 1);
    }
    
    // 计算目标值
    long long target = (long long)a[idx1] + a[idx2];

    // 4. 写入 .in 文件
    string in_filename = to_string(case_id) + ".in";
    ofstream fin(in_filename);
    fin << n << " " << target << endl;
    for (int i = 0; i < n; ++i) {
        fin << a[i] << (i == n - 1 ? "" : " ");
    }
    fin << endl;
    fin.close();

    // 5. 运行标程并写入 .out 文件
    // 注意：虽然我们预设了 idx1 和 idx2，但由于可能有重复元素，
    // 标程找到的下标可能与预设的不同（但值是正确的）。
    // 以标程输出为准，保证测评一致性。
    pair<int, int> result = solve(n, target, a);
    
    string out_filename = to_string(case_id) + ".out";
    ofstream fout(out_filename);
    fout << result.first << " " << result.second << endl;
    fout.close();

    cout << "Generated Case " << case_id << ": N=" << n << " Target=" << target << " Sol=(" << result.first << "," << result.second << ")" << endl;
}

int main() {
    // 优化：不使用 I/O 同步，虽然对于生成器不是瓶颈，但是好习惯
    ios::sync_with_stdio(false);
    
    for (int i = 1; i <= TOTAL_CASES; ++i) {
        generate_case(i);
    }

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

复杂度分析与生成器优化说明

1. 时间复杂度：

   • 生成过程：主要消耗在 std::sort 上，复杂度为 $O(N \log N)$。
   • 求解过程：运行了一次双指针，复杂度为 $O(N)$。
   • 总复杂度：对于 $N=30000$ 的最大测试点，总操作次数在 $10^5$ 级别，现代 CPU 可以瞬间完成所有 10 个测试点的生成。
   • 优化：避免了递归结构，使用了 vector 管理内存，完全没有爆栈风险。

2. 空间复杂度：

   • 使用了 vector<int> 存储 $30000$ 个整数，占用内存极小（约 120KB），远低于一般题目限制的 256MB。

测试点覆盖详情表

这个生成器可以直接在本地运行，生成的文件符合题目要求格式，可以直接上传至 OJ 后台作为评测数据。

这是一个标准的NOI竞赛风格题解。作为教练，我将从代码实现、复杂度分析、以及考场上的注意事项三个方面为你详细拆解。

1. NOI 标准 C++14 参考代码

这份代码可以直接在 NOIP/CSP/NOI 系列比赛环境中使用。

/**
 * 题目：两数之和 II - 输入有序数组 (Two Sum II)
 * 算法：双指针 (Two Pointers)
 * 语言标准：C++14
 * 
 * 考点：利用数组的"单调性"进行线性时间查找
 */

#include <iostream>
#include <vector>
#include <algorithm> // 虽然本题主要逻辑不需要，但在竞赛中通常习惯包含

using namespace std;

// 使用 const 引用传递 vector，避免大数据拷贝，养成良好习惯
// 虽然本题在 main 中直接写也可以，但在做复杂大题封装函数时这点很重要
void solve() {
    int n;
    long long target; // 习惯性使用 long long 防止目标值溢出（虽然本题数据范围 int 足够）
    
    if (!(cin >> n >> target)) return;

    // 预分配空间，避免 vector 动态扩容带来的常数级开销
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // --- 核心算法：双指针 ---
    // l (left) 指向最小值端，r (right) 指向最大值端
    int l = 0; 
    int r = n - 1;

    // 循环条件 l < r。
    // 注意：不能是 l <= r，因为题目要求两个数下标不同
    while (l < r) {
        // 计算当前和
        // 【易错点1】虽然本题 A[i] <= 1000，但在通用场景下，两数相加容易爆 int
        // 所以计算中间结果建议强转 long long
        long long current_sum = (long long)a[l] + a[r];

        if (current_sum == target) {
            // 【易错点2】题目要求输出下标从 1 开始
            cout << l + 1 << " " << r + 1 << endl;
            return; // 题目保证唯一解，找到后立即结束
        } 
        else if (current_sum > target) {
            // 当前和太大了 -> 需要减小和
            // 因为数组有序，a[l] 已经是最小的了，只能让 r 左移找更小的数
            r--; 
        } 
        else { // current_sum < target
            // 当前和太小了 -> 需要增大和
            // 因为 a[r] 已经是最大的了，只能让 l 右移找更大的数
            l++;
        }
    }
    
    // 理论上题目保证有解不会运行到这里
}

int main() {
    // 【考场必备优化】
    // 关闭 C++ 标准流与 C 标准流的同步，解除 cin 与 cout 的绑定
    // 可以显著提升 I/O 速度，防止大数据量下 TLE (Time Limit Exceeded)
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

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

时间复杂度分析

• 思考过程：
  • 我们定义了两个指针 l 和 r。
  • 在每一次循环中，要么 l 增加 1（向右走），要么 r 减少 1（向左走）。
  • l 从 0 开始，r 从 $n-1$ 开始。两者在相遇时停止。
  • 这意味着 l 和 r 走过的总路程最多是 $n$。
  • 循环内部的操作（加法、比较）都是 $O(1)$ 的。
• 结论：时间复杂度为 $O(n)$。
  • 这是处理有序数组查找问题的最优阶。相比于二分查找的 $O(n \log n)$ 和暴力枚举的 $O(n^2)$，这是质的飞跃。

空间复杂度分析

• 思考过程：
  • 我们需要存储输入的数组，占用 $O(n)$ 空间。
  • 但在计算过程中，我们只使用了 l, r, current_sum, n, target 这几个变量。
  • 这些变量占用的空间是固定的，不随数据规模 $n$ 的增长而增长。
• 结论：额外空间复杂度为 $O(1)$。
  • 这满足了题目中“只使用常量级额外空间”的要求。如果使用哈希表（std::map 或 std::unordered_map），额外空间复杂度会变成 $O(n)$，且常数较大。

3. 时间复杂度优化建议（教练批注）

在 OI 竞赛中，如果你的算法复杂度已经是 $O(n)$，通常不需要再进行算法逻辑上的优化了，重点应转向常数优化和I/O优化。

1. I/O 读写优化（必须掌握）：

   • 题目数据量 $N$ 如果达到 $10^5$ 或 $10^6$ 级别，cin / cout 可能会因为缓冲区同步问题变慢。
   • 代码中的优化：ios::sync_with_stdio(false); cin.tie(nullptr); 是 C++ 选手的“起手式”，必须死记硬背。
   • 极端情况：如果数据量极大（如 $5 \times 10^6$ 个整数读入），可以使用 scanf / printf 或者手写快读（Fast I/O）。但在本题 $N=30000$ 的范围内，标准流优化足够了。

2. 避免不必要的内存分配：

   • vector<int> a(n); 是最好的写法。
   • 不要写成 vector<int> a; 然后在循环里 a.push_back(x);。虽然 push_back 均摊复杂度是 $O(1)$，但频繁的动态扩容和内存拷贝在常数上比直接分配慢。

3. 算法层面的伪优化（二分查找）：

   • 有同学会问：“我能不能固定左边，然后右边二分查找？”
   • 教练回答：可以，但那是 $O(n \log n)$。在 $N$ 很大时，$\log N$ 大约是 15~20 倍的常数差距。双指针的 $O(n)$ 是一遍扫描，利用了每一个元素的信息，没有多余的比较，这才是针对“有序”特性的极致利用。