UVA10202 Pairsumonious Numbers 题解

· · 题解

You can view the English version of this solution.

参考了 this。

我第一眼看这题的时候，首先想到了通过求 \sum a_i 再推导的方式，然后发现当 n>3 时没前途了。

不妨令序列单调不减，即 a_i\le a_{i+1}。

把这些和列出来：

\begin{array}{} a_1+a_2 & a_1+a_3 & a_1+a_4 & \cdots & a_1+a_n \\ & a_2+a_3 & a_2+a_4 & \cdots & a_2+a_n \\ & & a_3+a_4 & \cdots & a_3+a_n \\ & & & \ddots & \vdots \\ & & & & a_{n-1}+a_n \end{array}

显然的，有 a_1+a_2 是其中最小的。于是，当知道 a_1 时能确定 a_2。我们在表中删去第 1 列，此时又有 a_1+a_3 是最小的，那便可以确定 a_3。以此类推，我们仅需知道 a_1 便可推出完整序列。用 multiset 维护之，复杂度 \mathcal{O}(n^2\log n)。

问题转化为如何确定 a_1。

一种显然的方法是枚举 1\le a_1\le\lfloor\frac{a_1+a_2}2\rfloor。这么做复杂度为 \mathcal{O}(V\cdot n^2\log n)，可通过 P1286。

考虑最开始的思路，当 n=3 时我们是可以简单的通过求和再推导算出完整序列。而 a_1+a_2 为最小值，a_1+a_3 为次小值，仅有 a_2+a_3 不确定。不难发现，其一定为前 n 小的，这是由于只有表中第一行可能比它小。于是枚举即可。

复杂度 \mathcal{O}(n^3\log n)。

提示：UVA 仅支持 C++11，所以得将 multiset 改为 map 之类维护。