2025传智杯复赛第二场官方题解 | T3 | #数组重乘法#

题意

给定一个包含 个正整数的数组，求重新排列后相邻两项乘积之和 的最大值。

题解

根据排序不等式的思想，为了最大化相邻元素的乘积之和，应当尽可能让较大的数字彼此靠近，较小的数字放置在两端，最优的排列形态应当呈现“单峰”结构。

具体构造时，先将原数组从大到小排序，把最大的元素放入双端队列。接着，对于剩余的元素，每次比较队列两端的元素大小，将当前元素拼接在较大的一端即可。除此之外，直接将升序排序后的数组按奇偶下标交错分配也是一种等价的做法。

复杂度

• 时间复杂度：
• 空间复杂度：

参考代码与链接

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    sort(a.begin(), a.end(), greater<i64>());
    
    deque<i64> dq;
    dq.push_back(a[0]);
    
    for (int i = 1; i < n; ++i) {
        if (dq.front() > dq.back()) {
            dq.push_front(a[i]);
        } else {
            dq.push_back(a[i]);
        }
    }
    
    i64 ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        ans += dq[i] * dq[i + 1];
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}