Abc 071 Make a Rectangle

问题陈述

我们有 N 根厚度可忽略的木棍。第 i 根木棍的长度为 A i 。

Snuke 想从这些木棍中选择四根不同的木棍，并使用这些木棍作为边，形成一个矩形（包括正方形）。求出矩形的最大可能面积。

约束

4≤N≤10 5

1≤A i ≤10 9 A i 为整数。

输入

输入来自标准输入，格式如下：

N

A 1 A 2 ... A N

输出

打印矩形的最大可能面积。如果无法形成矩形，则打印 0。

样例输入 1

6

3 1 2 4 2 1

样例输出 1

2

可以形成 1×2 矩形。

样例输入 2

4

1 2 3 4

样例输出 2

0

无法形成矩形。

示例输入 3

10

3 3 3 3 4 4 4 5 5 5

示例输出 3

20

为了制作一个 H × W 的矩形，您需要两根长度为 H 的木棍和两根长度为 W 的木棍。如果 H = W，则需要四根长度为 H 的木棍。在上述约束下，您应该贪婪地选择最长的木棍。首先，按降序对 {Ai} 进行排序。由于排序后相同长度的木棍会分组在一起，因此我们可以计算每种长度的木棍数量。我们按长度的降序检查木棍，并执行以下操作：

• 如果我们没有选择任何木棍，并且找到四根（或更多）相同长度的木棍，则选择它们并完成该过程。

• 如果我们没有选择任何木棍，并且找到两根或三根相同长度的木棍，则选择它们（并继续该过程）。

• 如果我们选择了两根木棍，并且找到两根（或更多）相同长度的木棍，则选择其中两根并完成该过程。

• 否则，跳过当前长度的木棍。

如果经过此过程我们成功选择了四根棍子，则打印矩形的面积。否则，打印 0。

官方题解是用数组排序，那个比较费脑子，我用的hashmap，但是用hashmap总有一个案例通不过，也不知道是什么原因，

于是就用treemap来做了，还好过了，就是对于value>1的值去依次保存当前最大的key，还有当前第二大的key。如果value>3也就是说可以组成正方形，那么更新当前第二大的key跟第一大的相等，依次遍历即可。

初始值设置成0，因为有可能组不成矩形。