You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

已知一个长度为 $n$ 的正整数序列 $a_0,...,a_{n-1}$，且存在一个整数 $k\in[0,n)$，使得 $a_0,...,a_{k-1}$ 严格单调递增，$a_{k},...,a_{n-1}$ 严格单调递减，$a_k$ 为该序列当中的最大值。

你需要设计一个算法找出对应的 $k$。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 peak.h。

你需要实现一个函数 int findPeak(int)，传入参数为 $n$，表示正整数序列的长度；返回值见题目描述，为对应的单峰位置 $k$。

你可以调用函数 int get(int)，参数是一个介于 $0$ 到 $n-1$ 之间的整数 $x$，返回值为 $a_x$。你无法得知具体的正整数序列，只能使用 get 函数获取。当 get 调用次数超过 $100$，或者传入参数越界，则会报 Runtime Error。

以下我们给出一个代码提交实例（会固定返回答案 114514，仅作为示例，不保证能得分）：

#include "peak.h"
int findPeak(int n)
{
    return 114514;
}

你不需要，也不应该，实现主函数。

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 peak.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

7
2 9 15 19 22 4 3

4

样例 1 解释

该样例遵循白盒交互库的形式。

输入第一行为 $n$，第二行为 $a_0,\cdots a_{n-1}$，返回的是峰值对应的秩，因此输出不是 22 而是 4。

子任务

对于所有数据，保证 $1\le n\le 10^6,~1\le a_i\le 2\times 10^9$。

提示

我们需要一个 $O(\log n)$ 的算法解决本问题。此外，你的代码需要能够处理特殊的边界情况。

在考场上，你还需要能够对着代码说明其正确性以及时间算法复杂度的正确性，请务必注意这一点。

来源

826 考研初试 2018《数据结构》算法大题（2）