题目描述

难度分:$1600$

输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(2 \leq a[i] \leq 10^6)$。

你有$n$根木棍，$a[i]$表示第$i$根木棍的长度。

你可以缩短某些木棍的长度。

这些被缩短的木棍，长度只能减少$1$。

你需要选择$4k$根木棍，制作$k$个矩形（一根木棍只能在一个矩形中）。输出这些矩形面积之和的最大值。

输入样例$1$

4
2 4 4 2

输出样例$1$

8

输入样例$2$

4
2 2 3 5

输出样例$2$

0

输入样例$3$

4
100003 100004 100005 100006

输出样例$3$

10000800015

算法

贪心

根据矩形的边至少是成对相等的（或者是个正方形）很容易发现的一点就是，所有木棍长度的频数都要尽量为偶数，这样才能最高效地利用木棍。

预处理

先遍历$a$数组得到一个木棍长度的计数器$raw\_counter$（可以用有序表），然后从长到短遍历木棍的长度，对于长度为$k$的木棍，如果发现它有奇数根，就拿一根出来削成$k-1$，这样处理出来一个新的频数表$counter$。

大根堆贪心

把$counter$中的键值对$(k,v)$存入一个大根堆后贪心，先取出堆顶元素，优先构建面积更大的正方形，$4$根$4$根地取，直到堆顶长度的木棍不足$4$根，再考虑让它和次长的木棍构成长方形。假设最长的木棍（长度$k_1$）还剩下$cnt_1$根，次长的木棍（如果有次长木棍才进行这一步，设其长度$k_2$）还剩下$cnt_2$根，它们就能构成$\frac{min(cnt_1,cnt_2)}{2}$个面积为$k_1 \times k_2$的矩形。周而复始直到无法再构成矩形。

复杂度分析

时间复杂度

预处理使用的是有序表，需要遍历$O(n)$次，每次操作的时间复杂度为$O(log_2n)$，因此时间复杂度为$O(nlog_2n)$。贪心是不断弹出堆顶，但是可能会存在插入堆的操作，而堆中元素的规模为$O(n)$，因此时间复杂度为$O(nlog_2n)$。算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间消耗的瓶颈是两个计数器和大根堆，都是$O(n)$规模的，这也是算法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;

const int N = 100010;
int n, a[N];

int main() {
    scanf("%d", &n);
    map<int, int> counter, raw_counter;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        counter[a[i]]++;
        raw_counter[a[i]]++;     // 原始频数
    }
    for(auto it = raw_counter.rbegin(); it != raw_counter.rend(); it++) {
        int k = it->first, v = it->second;
        if(counter[k]&1) {
            // 长度为k的木棍有奇数根，就拿一根原始的出来削短（因为削只能削原始的棍子）
            counter[k]--;
            if(counter[k] == 0) counter.erase(k);
            if(k > 1) {
                counter[k - 1]++;
            }
        }
    }
    priority_queue<PII> heap;
    for(auto&[k, v]: counter) {
        if(!(v&1)) heap.push({k, v});
    }
    LL ans = 0;
    while(heap.size()) {
        auto t1 = heap.top();
        heap.pop();
        while(t1.second >= 4) {
            ans += (LL)t1.first*t1.first;
            t1.second -= 4;
        }
        if(t1.second && heap.size()) {
            auto t2 = heap.top();
            heap.pop();
            LL cnt = min(t1.second, t2.second);
            ans += cnt/2*t1.first*t2.first;
            t1.second -= cnt;
            t2.second -= cnt;
            if(t1.second) heap.push(t1);
            if(t2.second) heap.push(t2);
        }
    }
    printf("%lld\n", ans);
    return 0;
}