题解：P16494 樱蕊初含雪，惜春时易逝

Sunrise_up · 2026-05-16 16:32:09 · 题解

求点赞 qwq！

题意好难懂，于是翻译一下。

题意

有种子：白 x，红 y，黄 z，总数 n=x+y+z。

把 n 粒种子种到 n 个花盆，第 i 个花盆种出的花美观度为 a_i。每个花盆分配一种颜色。

种完后，需要进行两两配对，只有颜色不同的花才能配对。总美观度，是在所有配对方案下，成功配对的花的美观度之和的最大值。

对于所有的种植方案，求总美观度的最小值。

思路

注意到 x\le y\le z。

考虑什么时候能尽量配完：

• 当 x+y<z 时，另外两色总数太少，最多只能凑出 x+y 对花。可以发现当凑出 x+y 对花的情况下总美观值是最大的。凑出 x+y 对花的情况下，总美观值为白色的花、红色的花、黄色的花中最大的 x+y 朵之和。想要总美观值最小，只能用最小 x+y 朵搭配最大 x+y 朵两两组合求和。
• 当 x+y\ge z 时，几乎可以全部配对，仅剩余 n\bmod 2 朵无法配对。发现无论如何答案都为前 2\lfloor\frac{n}{2}\rfloor 大的花之和。

所以需要排序。

代码

你开 long long 了吗？

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50001;
int t,n,x,y,z,a[N],ans;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>x>>y>>z,ans=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+n+1);
        if(x+y<z){
            for(int i=1;i<=x+y;i++)ans+=a[i]+a[n-i+1];
        }else{
            for(int i=1+(n&1);i<=n;i++)ans+=a[i];
        }
        cout<<ans<<'\n';
    }
}