begin

P11148 传送门

前置算法

贪心 + 排序 + 枚举

思路

首先根据读题可知，所有类型的零食都有一个妙值，并且每一段同种零食的第一个妙值不计算在内，并且我们必须吃掉所有零食。我们需要求最大的妙值之和。

根据贪心策略，我们可以将整个妙值数列分为两部分：正数和负数（0 不对答案产生影响）。

正数对最终答案起到积极作用，所以我们要尽可能拿下所有正数。

而负数对答案起到消极作用，所以我们要尽可能将负数置于一段同种零食的开头（抵消掉）。

不难想出，如果想尽量消掉更多负数，两种零食的数量最多相差 1。

这样我们就可以先将妙值升序排列然后通过枚举一种零食的数量，直接得出另一种零食的数量，然后用一个足够小的 ans 维护最大值。

如果还有不懂请看代码 \downarrow

时间复杂度（不算排序）

Code

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll t,n,m,a[100010],b[100010],tota[100010],totb[100010],ans;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while (t--) // 偷个懒~
    {
        ans=LLONG_MIN; // 这够小了吧
        cin>>n;
        for (ll i=1;i<=n;i++)
            cin>>a[i];
        cin>>m;
        for (ll i=1;i<=m;i++)
            cin>>b[i];
        sort(a+1,a+n+1); // 简单的升序排序
        sort(b+1,b+m+1); // 注意这里是 b+m+1 不是 b+n+1 。。
        memset(tota,0,sizeof(tota)); // 初始化
        memset(totb,0,sizeof(totb));
        for (ll i=n;i>=1;i--)
            tota[i-1]=tota[i]+a[i]; // 计算以 a[i] 开始的妙值和
        for (ll i=m;i>=1;i--)
            totb[i-1]=totb[i]+b[i]; // 计算以 b[i] 开始的妙值和
        for (ll i=1;i<=min(n,m);i++)
            ans=max(ans,max(tota[i]+totb[i],max(tota[i]+totb[i+1],tota[i+1]+totb[i])));
/* 三种情况。因为 max 函数一次只能比较 2 个数，所以用了一个嵌套以达到比较多个数的目的。另外不用考虑边界是因为初始化已经将范围外的数据全都设置为了 0 加的时候不影响原来的值 */
        cout<<ans<<"\n";
    }
    return 0; // 完结撒花~
}

end