这是本文档旧的修订版!
给定一个 $1\sim n$ 的排列,最多允许 $100$ 次询问,每次可以询问指定位置的值。
要求找到一个 $i$ 满足 $a_i\lt a_{i-1}$ 且 $a_i\lt a_{i+1}$,假定 $a_0=a_{n+1}=\infty$。
维护区间 $[l,r]$,满足 $a_l\lt a_{l-1},a_r\lt a_{r+1}$。于是当 $l=r$ 时答案位置确定。
接下来二分区间,如果 $a_m\lt a_{m+1}$,则将 $r$ 修改为 $m$,否则将 $l$ 修改为 $m$。于是可以使用 $\log n$ 次询问得到答案。
$ps.$ 比赛时乱搞了一个单测试点正确率为 $95\text{%}$ 的随机算法,我当时脑子指定是有什么问题。