你好！我是金牌教练。为了方便你快速搭建 OJ（在线判题系统）测试环境，我为你编写了这个集成化的数据生成器与标程（Generator & Solver）。

在“寻找峰值”这类题目中，数据构造的关键在于确保 $nums[i] \neq nums[i+1]$，并且通过构造单调序列、锯齿序列和大规模随机序列来全面测试选手的二分逻辑。

一、 测试点设计矩阵

二、 数据生成器 C++ 代码

该程序采用 C++14 标准。它会自动生成 1.in 到 10.out。为了确保 $nums[i] \neq nums[i+1]$，生成逻辑采用了增量随机法。

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

using namespace std;

typedef long long ll;

// --- 标程：最优解 O(log n) ---
int findPeakStd(int n, const vector<int>& nums) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[mid + 1]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

// --- 数据构造工具 ---
mt19937 rng(time(0));

// 生成 [min, max] 范围内的随机整数
ll randInt(ll min_v, ll max_v) {
    return uniform_int_distribution<ll>(min_v, max_v)(rng);
}

void make_data() {
    for (int t = 1; t <= 10; t++) {
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";
        ofstream fout(in_name);
        ofstream fans(out_name);

        int n;
        if (t <= 2) n = randInt(5, 10);
        else if (t == 3) n = 1;
        else if (t <= 5) n = 100;
        else if (t <= 7) n = 1000;
        else if (t == 8) n = 50000;
        else n = 100000;

        vector<int> nums(n);
        if (t == 3) {
            nums[0] = randInt(-1e9, 1e9);
        } else if (t == 4) { // 严格递增
            nums[0] = -1e9 + randInt(0, 1e5);
            for (int i = 1; i < n; i++) nums[i] = nums[i - 1] + randInt(1, 100);
        } else if (t == 5) { // 严格递减
            nums[0] = 1e9 - randInt(0, 1e5);
            for (int i = 1; i < n; i++) nums[i] = nums[i - 1] - randInt(1, 100);
        } else if (t == 6) { // A 字形
            int mid = n / 2;
            nums[0] = randInt(-1e8, 0);
            for (int i = 1; i <= mid; i++) nums[i] = nums[i - 1] + randInt(1, 100);
            for (int i = mid + 1; i < n; i++) nums[i] = nums[i - 1] - randInt(1, 100);
        } else if (t == 7) { // V 字形
            int mid = n / 2;
            nums[0] = randInt(1e8, 2e8);
            for (int i = 1; i <= mid; i++) nums[i] = nums[i - 1] - randInt(1, 100);
            for (int i = mid + 1; i < n; i++) nums[i] = nums[i - 1] + randInt(1, 100);
        } else { // 随机震荡
            nums[0] = randInt(-1e8, 1e8);
            for (int i = 1; i < n; i++) {
                int delta = randInt(1, 1000);
                if (rng() % 2) nums[i] = nums[i - 1] + delta;
                else nums[i] = nums[i - 1] - delta;
            }
        }

        // 写入 .in
        fout << n << "\n";
        for (int i = 0; i < n; i++) {
            fout << nums[i] << (i == n - 1 ? "" : " ");
        }
        fout << "\n";

        // 写入 .out (标程跑一遍)
        int ans_idx = findPeakStd(n, nums);
        fans << ans_idx << "\n";

        cout << "Test Case " << t << " [n=" << n << "] generated." << endl;
        fout.close(); fans.close();
    }
}

int main() {
    make_data();
    return 0;
}

三、 生成器关键细节分析

1. 文件大小控制：

   • 当 $n=10^5$ 时，每个整数约占 10~11 字节，单个 .in 文件约 1.1MB。
   • 10 个测试点总大小约 5MB。虽然略超“全套 2MB”的理想值，但在 $n=10^5$ 的 NOI 标准下，这是必须的。如果需要极度缩小，可将 $n=10^5$ 的点减少到 1 个。

2. 强制相邻不等：

   • 通过 nums[i] = nums[i-1] + delta（其中 $delta \ge 1$）来生成数据，完美规避了 $nums[i] == nums[i+1]$ 的非法情况，确保了二分的单调性判定有效。

3. 计算稳定性：

   • 非递归：标程使用 while 循环实现，杜绝了栈溢出风险。
   • 防溢出：在计算 mid 时使用了 l + (r - l) / 2。虽然下标不会溢出 int，但这是良好的竞赛编程习惯。

4. 区分算法复杂度：

   • $O(n)$ 的线性扫描在 $10^5$ 规模下通常耗时在 10ms~30ms。
   • $O(\log n)$ 的二分查找耗时趋近于 0ms。
   • 建议：在 OJ 上将此题时限设置为 0.05s (50ms)，这样可以精准地强制选手使用 $O(\log n)$ 算法，而过滤掉 $O(n)$ 算法。

四、 读题关键词总结 (OJ 命题视角)

1. “时间复杂度 $O(\log n)$”：这是命题人给出的死命令，意味着线性遍历哪怕能过也是“非标准解”。
2. “相邻元素不相等”：这是保证“二段性”的救命稻草，没有它，二分将无法通过局部比较判定方向。
3. “$nums[-1] = nums[n] = -\infty$”：隐含了“山脚下必有山顶”的性质，保证了答案一定存在。

同学，你可以运行这个生成器来检查你自己的代码对各种边界情况（单调序列、单点序列）的处理。加油！

你好！我是金牌教练。寻找峰值这道题非常有趣，它完美诠释了 “局部性质决定全局存在” 的数学思想。

在 NOI 竞赛中，虽然 $O(n)$ 的线性扫描通常能过 $10^5$ 的数据，但掌握 $O(\log n)$ 的二分法是区分普通选手与顶尖选手的关键，因为在更复杂的问题中（如高维峰值查找），线性复杂度会彻底失效。

版本 1：暴力扫描版 (Linear Scan)

思路提示： 最直截了当的方法。遍历数组，检查每一个元素是否满足比左边大且比右边大。 由于题目规定 $nums[-1] = nums[n] = -\infty$，所以：

1. 如果 $n=1$，索引 0 就是峰值。
2. 检查 $nums[0]$ 是否大于 $nums[1]$。
3. 检查 $nums[n-1]$ 是否大于 $nums[n-2]$。
4. 中间元素需满足 $nums[i] > nums[i-1]$ 且 $nums[i] > nums[i+1]$。

复杂度分析：

• 时间复杂度：$O(n)$。最坏情况下需要遍历整个数组。
• 空间复杂度：$O(n)$（存储输入数据）。

/*
 * 暴力扫描版：严格按照峰值定义检查
 * 易错点：数组越界处理（尤其是 0 和 n-1 处）
 */
#include <iostream>
#include <vector>

using namespace std;

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

    // 特判：只有一个元素
    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < n; i++) {
        bool left_ok = (i == 0) || (nums[i] > nums[i - 1]);
        bool right_ok = (i == n - 1) || (nums[i] > nums[i + 1]);
        
        if (left_ok && right_ok) {
            cout << i << endl;
            return 0; // 只要找到一个就退出
        }
    }
    return 0;
}

版本 2：线性爬坡版 (Linear Climb)

思路提示： 由于 $nums[-1] = -\infty$，只要数组开始增长（$nums[i] < nums[i+1]$），我们就处于上坡。 第一个满足 $nums[i] > nums[i+1]$ 的位置 $i$，一定是一个峰值。 为什么？因为既然它是第一个满足该条件的，说明它之前的元素都是递增的（即 $nums[i] > nums[i-1]$），而现在它又比右边大，它就是峰。

复杂度分析：

• 时间复杂度：$O(n)$。虽然比版本 1 简洁，但本质仍是线性。
• 空间复杂度：$O(1)$（不计数组）。

/*
 * 线性爬坡版：寻找第一个下降点
 * 逻辑：只要在上升，就还没到峰顶。一旦下降，当前点就是峰。
 */
#include <iostream>
#include <vector>

using namespace std;

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

    for (int i = 0; i < n - 1; i++) {
        // 如果当前点比右边大，由于前面一直在上升，这里就是峰值
        if (nums[i] > nums[i + 1]) {
            cout << i << endl;
            return 0;
        }
    }
    
    // 如果一直没找到，说明数组单调递增，最后一个元素是峰
    cout << n - 1 << endl;
    return 0;
}

版本 3：最优解 - 二分查找版 (Binary Search)

思路提示： 版本 2 的“爬坡”思想可以被二分加速。

1. 取中点 mid。
2. 比较 nums[mid] 和 nums[mid+1]。
3. 如果 nums[mid] < nums[mid+1]，说明右侧必有峰值（上坡必有顶）。
4. 如果 nums[mid] > nums[mid+1]，说明左侧（含 mid）必有峰值。

复杂度分析：

• 时间复杂度：$O(\log n)$。对于 $10^5$ 数据，仅需 17 次比较。
• 空间复杂度：$O(1)$。

/*
 * 二分查找版：NOI 满分标准代码
 * 关键点：利用局部单调性缩小搜索范围
 * 易错点：循环条件 L < R 以及 L = mid + 1 的细节
 */
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 提高 IO 速度
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    int left = 0, right = n - 1;
    
    // 使用左闭右开或左闭右闭逻辑。这里采用 L < R，最终 L == R 即为答案
    while (left < right) {
        // 防止溢出的中点写法
        int mid = left + (right - left) / 2;
        
        // 核心判定：往高处走
        if (nums[mid] < nums[mid + 1]) {
            // 右边更高，说明峰值在右侧区间 (不含 mid)
            left = mid + 1;
        } else {
            // 左边更高或相等(虽然题目说不等)，说明峰值在左侧区间 (含 mid)
            right = mid;
        }
    }

    // 循环结束时，left == right，指向其中一个峰值
    cout << left << endl;

    return 0;
}

时间复杂度优化建议与总结

1. 二段性分析： 通常二分查找需要全局有序，但本题告诉我们，只要能通过某种判定（相邻元素大小）排除掉一半不可能包含特定解（其中一个峰值）的区间，就可以使用二分。这在处理复杂几何问题（如三分法找极值）时非常有用。

2. 边界保护： 在版本 3 中，mid = left + (right - left) / 2。 当 left < right 时，mid 永远能够取到 left 但永远取不到 right。 这意味着 mid + 1 永远不会导致数组下标越界（最大为 right）。这是竞赛中处理边界的小技巧。

3. 数据范围注意事项： 题目中 $nums[i]$ 的范围达到了 $2^{31}-1$，这是 int 的极限。在进行比较时没问题，但如果你在代码中涉及 nums[i] + nums[j] 这种操作，必须开启 long long，否则会溢出导致逻辑错误。

4. 优化建议： 对于 $N=10^5$ 的规模，std::vector 的分配耗时可以忽略。但如果 $N$ 达到 $10^6$ 以上，建议使用静态数组 int a[1000005]，以获得更极致的运行速度。

总结：这道题考察的是你对二分本质的理解——二分不是为了找“值”，而是为了通过“判定”不断缩小“候选区间”。加油！