C++ 算法：求 N 根木棒拼成的最大长方形面积

C++ 算法：求 N 根木棒拼成的最大长方形面积

问题描述：

有 N 根可以忽略粗细的木棒，第 i 根木棒的长度为 Ai。 Snuke 君要从这 N 根木棒中选出 4 根来拼出一个长方形（正方形也是长方形的一种）。

求出可以拼出的长方形的最大面积。

输入：

第 1 行，一个正整数 N 第 2 行，N 个正整数 A1, A2, ⋯, AN，以空格分隔

输出：

输出可以拼出的长方形的最大面积，如果无法拼出长方形，输出 0

样例输入：

6
3 1 2 4 2 1

样例输出：

2

提示：

4≤N≤106, 1≤Ai≤106

C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<int> sticks(N);
    for (int i = 0; i < N; i++) {
        cin >> sticks[i];
    }
    
    sort(sticks.begin(), sticks.end(), greater<int>());
    
    int maxArea = 0;
    for (int i = 0; i < N-3; i++) {
        if (sticks[i] == sticks[i+1]) {
            for (int j = i+2; j < N-1; j++) {
                if (sticks[j] == sticks[j+1]) {
                    maxArea = max(maxArea, sticks[i] * sticks[j]);
                }
            }
        }
    }
    
    cout << maxArea << endl;
    
    return 0;
}

代码解释：

1. 使用 vector 存储木棒长度，并使用 sort 函数按照降序排列木棒长度。
2. 使用两层循环遍历木棒长度，寻找两个相同长度的木棒作为长方形的长和宽。
3. 每次找到满足条件的两个木棒，就计算长方形面积并更新 maxArea 的值。

示例：

对于样例输入，代码将输出 2。因为可以用长度为 3 和 2 的两根木棒拼成一个长方形，面积为 6。

总结：

本代码利用了排序和循环遍历的思想，有效地找到了可以用 N 根木棒拼成的最大长方形面积。