【题解】CF1634D Finding Zero 题解

题意

交互库中存在一个非负整数数列 $a_i$ 。
给定数列的长度 $n$ ，每次可以选择三个不同的位置 $i,j,k$ 进行询问，交互库会返回数列中对应的三个数的极差，即 $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$ 。
现保证数列中恰好存在一个 $0$ ，请用最多 $n \cdot 2-2$ 次询问求出 $0$ 的位置。
回答时可以回答两个位置，只要有一个位置是正确的即可。
$\mathcal{Data~Range}$ ： $t$ 组数据， $1 \le t \le 500$ ， $4 \le n \le 1 \times 10^3$ ， $\displaystyle \sum_{i = 1}^t n_i \le 3 \times 10^3$ 。

题解

我们知道，整个序列是非负的，并且恰好存在一个 $0$ ，说明 $0$ 是数列的最小值。换句话说， $0$ 是数列的极值。

同时，我们在回答时可以回答两个位置，这启发我们：如果我们已经知道数列中有两个位置分别对应了数列的两个极值（这里特指一个最大值和一个最小值），那么我们回答这两个位置即可。

所以算法的大致框架就出来了：确定数列的极值位置。

首先，我们可以先固定两个位置（下文以 $1,n$ 为例），询问它们和其它所有位置 $i$ 的值（即所有的 $\max(a_1, a_n, a_i) - \min(a_1, a_n, a_i)$ ）。这一步一共用去了 $n-2$ 次询问。

得到了所有位置的值之后，我们就需要分情况讨论了。

$\mathcal{A}.$ 所有值中的最大值和最小值相等

最大值和最小值相等，其实就说明了所有数都相等。

也就是说， $a_1$ 和 $a_n$ 两个位置有可能直接对应了最大值和最小值，因为无论怎样询问，得到的答案都是 $|a_1 - a_n|$ 。

但这是唯一的情况吗？显然不是，因为还存在另外一种情况：

如果把所有数放在数轴上，发现它们最多只有 $4$ 个本质不同的数（且至少有 $3$ 个本质不同的数），并且 $a_{2 \sim n - 1}$ 这些数关于一个数的位置或者两个数正中间的位置轴对称，那么 $a_1$ 和 $a_n$ 也可能对应了这个对称轴所对应的一个数或者两个数。

举两个例子（分别对应一个数和两个数做为对称轴的情况）：

$\begin{matrix} a_i: 1,2,0,2,1 \\ a_i: 1,3,0,3,2 \end{matrix}$

第一个例子中， $1$ 即为对称轴，并且 $a_1=a_n=1$ ，可以发现只出现了 $3$ 个本质不同的数，并且每一个位置的值都相等。

第二个例子中， $1$ 和 $2$ 正中间的位置即为对称轴，并且有 $a_1 = 1,a_n=2$ ，可以发现只出现了 $4$ 个本质不同的数，并且同样可以发现每一个位置的值都相等。

在这一种情况中， $a_1,a_n$ 并非极值，但是它满足了前提条件 $\mathcal{A}$ 。然而，单凭前 $n-2$ 次询问并不能区分这两种情况。

所以这个时候，我们再次拿出两个位置 $2$ 和 $n - 1$ ，再做 $n - 2$ 次询问得到每个位置的值（因为 $n\ge 4$ ，所以选择这两个位置不会有问题）。

这个时候，我们就得继续分情况讨论了。

$\alpha.$ 所有值中的最大值和最小值仍然相等

上面我们讨论了，如果两个位置做 $n - 2$ 次询问得到的所有值都相等，那么只会对应上述的两种情况。

并且，我们可以发现一个十分巧妙的结论： $a_1,a_n$ 和 $a_2,a_{n - 1}$ 这两对数，一定分别对应这两种情况。

证明：

如果两个位置分别对应了一个最大值和一个最小值，由于最小值为 $0$ 且只有一个，所以另一对数一定不会对应这种情况。

如果两个位置分别对应了对称轴所对应的一个或两个数，由于对称轴上不会出现除这两个位置之外的任何位置（否则最小值就为 $0$ ，由于所有的 $a_i$ 不会全部相等，那么其必然小于最大值），所以另一对数也不会对应这种情况。

证毕。

所以，如果我们能区分这两种情况，那么就可以得到极值的两个位置。

区分它们很简单：如果做 $n - 2$ 次询问后，一对数所得到的值大于另一对得到的值（没有歧义，因为两对数得到的所有值分别是相等的），说明前者是极值的位置，反之说明后者是极值的位置。

理由很简单：整个序列的极差一定会大于等于子序列的极差，而等于的情况在这里一定不会出现。

$\beta.$ 所有值中的最大值和最小值不相等

这里我们也得分情况讨论：

$1,n$ 两个位置对应的是最大值和最小值，而 $2,n - 1$ 两个位置对应了任意两个不属于 $\mathcal{A}-\alpha$ 情况的两个数；
$1,n$ 对应的是对称轴所对应的一个或两个数，而 $2,n - 1$ 两个位置对应了两个最大值。

对于第一种情况，我们直接输出 $1,n$ 两个位置即可。

对于第二种情况，我们找到 $2,n-1$ 两个位置询问 $n - 2$ 次后获得的最大值所对应的位置，这个位置即为 $0$ 所在的位置。

区分也很简单，我们直接通过 $\mathcal{A}-\alpha$ 情况中得出的结论来区分即可：如果做 $n - 2$ 次询问后， $a_2,a_{n-1}$ 这对数获得的最大值大于 $1,n$ 获得的最大值，那么为情况 $\mathcal{A}-\alpha-2$ ，否则为情况 $\mathcal{A}-\alpha-1$ 。