codeforces1369C（贪心）

题意描述

Lee just became Master in Codeforces, and so, he went out to buy some gifts for his friends. He bought n integers, now it’s time to distribute them between his friends rationally…

Lee has n integers a1,a2,…,an in his backpack and he has k friends. Lee would like to distribute all integers in his backpack between his friends, such that the i-th friend will get exactly wi integers and each integer will be handed over to exactly one friend.

Let’s define the happiness of a friend as the sum of the maximum and the minimum integer he’ll get.

Lee would like to make his friends as happy as possible, in other words, he’d like to maximize the sum of friends’ happiness. Now he asks you to calculate the maximum sum of friends’ happiness.

定义幸福度为每个人能获得的最大礼物和最小礼物之和，求最多的幸福度是多少

思路

要想使幸福度最大，那么我们就要最大程度的利用大礼物，所以我们可以对每个人能够获得的礼物降序排序，然后按照第k大，第k-1大…第1大的顺序来分。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=2*1e5+10;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int a[N],b[N];
void solve(){
    int n,k;cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<k;i++) cin>>b[i];
    sort(a,a+n);
    sort(b,b+k);
    reverse(b,b+k);
    int l=0,r=n-k;
    LL ans=0;
    for(int i=0;i<k;i++){
        ans+=a[r];
        if(b[i]==1) ans+=a[r];
        else ans+=a[l];
        r++;
        l+=b[i]-1;//中间的数没有贡献，直接跳过
    }
    cout<<ans<<endl;
}
int main(){
    IOS;
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}