G5013 [GESP202503 五级] 平均分配 题解

知识点：贪心、排序、差值转换。

解题思路

先假设2n项全部选方案c，总和为base；改选方案b的收益是b_i-c_i。选择收益最大的n项改为b。

为什么正确

总目标为固定base加n个独立差值，取最大的n个差值由交换论证最优。

易错点

即使最大n个差值中有负数，也必须恰好选n个；和与差值用long long。

复杂度

时间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>b(2*n),d(2*n);
    for(auto &x:b)cin>>x;
    long long ans=0;
    for(int i=0;i<2*n;i++) {
        long long c;
        cin>>c;
        ans+=c;
        d[i]=b[i]-c;
    }
    sort(d.rbegin(),d.rend());
    for(int i=0;i<n;i++)ans+=d[i];
    cout<<ans;
}

说明

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