题解：CF1764C Doremy's City Construction

又来水题解了。这是我们模拟赛的 T1。

分析

其实看懂样例就能会一半。

先看样例：

CPP

6
5 2 3 1 5 2

发现可以分成两部分，两两配对。

CPP

[1 2 2] [3 5 5] (ans=3*3=9)

CPP

12
7 2 4 9 1 4 6 3 7 4 2 3

发现还是可以分成两部分，两两配对。

CPP

[1 2 2 3 3] [4 4 4 6 7 7 9] ans=5*7

因此我们联想到二分图（也可以不联想）。

我们可以先排一个序，分成大小为

L,R

的两部分（这两部分必须要没有相同部分，也就是说排序后，分割点两侧的数不相同），有：

ans=\max(ans,L\times R)

其中

R=n-L

。

所以只需要使得

L^2+nL

最大即可。

总时间复杂度

O(Tn\log n)

，慢在排序。