题解：P11148 [THUWC 2018] 零食

Nostopathy · 2024-10-03 17:50:16 · 题解

solution

我们把两种物品的权值没有被计入总和称为相互抵消。

因为相互抵消的两种物品最多只可能相差 1，所以通过枚举其中一种零食被抵消的数量，另外一种也能随之确定。

为了让得到的答案最大，我们需要贪心抵消权值较小的物品。所以对 a 和 b 排序后遍历一遍，不难求解。

代码贴上来：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void read(int &n)
{
    int x=0,F=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            F=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    n=x*F;
}
void write(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
    return;
}
const int maxn=1E5+10;
int n, m, a[maxn], b[maxn];
int tota[maxn], totb[maxn];
int f__a(int x)
{
    if(x<=n)
    {
        return tota[x];
    }
    return 0;
}
int f__b(int x)
{
    if(x<=m)
    {
        return totb[x];
    }
    return 0;
}
void work()
{
    read(n);    for(int i=1; i<=n; ++i) read(a[i]);
    read(m);    for(int i=1; i<=m; ++i) read(b[i]);
    sort(a+1, a+n+1);
    sort(b+1, b+m+1);

    tota[n+1] = 0;  totb[m+1] = 0;
    for(int i=n; i; --i)    tota[i]=tota[i+1]+a[i];
    for(int i=m; i; --i)    totb[i]=totb[i+1]+b[i];
    int ans = LLONG_MIN;
    for(int i=1; i<=min(n, m); ++i)
    {
        if(i<=n&&i<=m)
            ans=max(f__a(i+1)+f__b(i+1), ans);
        if(i+1<=n&&i<=m)
            ans=max(f__a(i+2)+f__b(i+1), ans);
        if(i<=n&&i+1<=m)
            ans=max(f__a(i+1)+f__b(i+2), ans);
    }
    write(ans);
    cout << endl;
}
signed main(){
    //泥嚎，写题吧骚年
    int T;  read(T);
    while(T--) { work(); }
    return 0;
}

你的一个赞，对你只是举手之劳，对我却是最好的鼓励。

谢谢。