Codeforces Round #703 Guessing the Greatest - 二分

题意

这是一道交互式的问题。

存在一个长度为$n$的数组$a$,其中所有的数字都是不同的。

现在你最多可以做20次查询(Easy version可以做40次)。每次查询你需要输出一个区间,然后题目会通过输入给你这个区间中第二大的数的下标。

查询完毕后,你需要输出数组中,最大的数的下标。

题解

我们第一步先查询$[1,n]$,得到整个数组中第二大的下标位置,于是可以得到下图:

我们将区间分为两半,并且查询$2^{nd}$所在的一侧。于是我们大概能得到下图:

如果$1^{st}$在这一侧,则必然返回$2^{nd}$的下标。相反,则必然返回$3^{rd}$的下标。

现在我们继续将可能的区间分为两半,再次查询$2^{nd}$所在的一侧。如果$2^{nd}$在区间范围外,就延申到$2^{nd}$一起查询。具体查询如下图:

于是我们就又把问题的规模缩小了一半。不断重复,我们就能在$log(n)$的次数内把可能的区间长度压缩到1。

代码

Submission #113663139 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论