题解：P11960 [GESP202503 五级] 平均分配

CSP_S_2023_T2 · 2025-03-24 08:35:49 · 题解

思路

首先，我们假设所有物品全部卖给小 B，则收入为 \sum_{i=1}^{2n}b_i。

而第 i 件物品从卖给小 B 变成卖给小 C 对收入的贡献为 c_i-b_i。

所以我们只需对 c_i-b_i 进行排序，选出前 n 个最大的，求和并加上全部卖给小 B 的收入即可。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,b[200005],c,a[200005],ans;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n*2;i++) cin>>b[i],ans+=b[i];  //全部卖给小 B 的收入
    for(int i=0;i<n*2;i++) cin>>c,a[i]=c-b[i];   //记录第 i 件物品对答案的贡献
    sort(a,a+n*2,greater<long long>());          //从大到小排序
    for(int i=0;i<n;i++) ans+=a[i];              //更新答案
    cout<<ans;
    return 0;   //完结撒花
}