G5023 [GESP202606 五级] 排排坐 题解

知识点：贪心、排序、前缀累计。

解题思路

将数值降序排列，依次维护前缀和，并把每个前缀和累加到总答案。

为什么正确

前面位置的数被计入更多后缀前缀和，大数放在较大系数位置，由交换论证总和最大。

易错点

这里目标是最大值，应降序；答案是前缀和之和而非单纯所有元素之和。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>a(n);
    for(auto &x:a)cin>>x;
    sort(a.rbegin(),a.rend());
    long long s=0,ans=0;
    for(long long x:a) {
        s+=x;
        ans+=s;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。