题解：CF1764C Doremy's City Construction

UnionRE · 2025-11-23 19:43:00 · 题解

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

题目

分析

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

先看样例：

6
5 2 3 1 5 2

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

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

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

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

[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)，慢在排序。