题解 P5470 【[NOI2019]序列】

· · 题解

感觉这题跟CF436E差不多 （甚至更简单）

一丶思路

首先有一种比较笨比的贪心，就是直接把a数组和b数组的最大的K个选出来，但是这样并不能满足有L个下标相同的条件。

按照反悔贪心的套路，考虑构造几种替换方案，使得每次交集+1，并且能够覆盖所有可能的情况，仔细思考有这么几种情况：

1.将一个选了b但没选a的位置x将a选上，并找到一个没选b但选了a的位置y将a退掉。这样的代价是a_x-a_y。

2.将一个选了a但没选b的位置x将b选上，并找到一个没选a但选了b的位置y将b退掉。这样的代价是b_x-b_y。

3.找到一个选了a但没选b的位置x，一个选了b但没选a的位置y，以及a,b都没选的位置z，将x,y选的都退掉，并将z的a,b都选上。这样的代价是a_z+b_z-a_x-b_y

4.找到一个选了a但没选b的位置x，一个选了b但没选a的位置y，以及a,b都选了的位置z，将z的a,b都退掉，并选上x的b，y的a。这样的代价是b_x+a_y-(a_z+b_z)。

对于这几种情况分别维护优先队列即可。注意在写的时候建议不要在改变状态时pop，而是在取出极值时将不合法情况pop掉。

具体维护可以看代码。

二丶代码

//W4P3R
#include<bits/stdc++.h>
#define inf 1e18
#define eps 1e-6
#define mp make_pair
#define pb push_back
#define re register ll
#define fr first
#define sd second
#define pa pair<ll,ll>
#define FOR(i,a,b) for(re i=a;i<=b;i++)
#define REP(i,a,b) for(re i=a;i>=b;i--)
#define lowbit(x) (x&(-x))
#define Z(x) (x>=mod?x-mod:x)
#define N 200010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
priority_queue<pa,vector<pa>,less<pa> >q1,q2,q3,q4,q5,q6,q7;
/*
q1:只选了b的x的a[x]
q2:只选了a的x的-a[x]
q3:只选了a的x的b[x]
q4:只选了b的x的-b[x]
q5:a,b都没选的x的a[x]+b[x]
q6:a,b都选了的x的-(a[x]+b[x])
*/
ll n,k,l;
ll a[N],b[N],ans[N];
//ans数组：0表示a,b都没选，1表示a没选b选了,2表示a选了b没选，3表示a,b都选了
pa p[N];
inline void add(ll x,ll op)
{
    if(op==0){q5.push(mp(a[x]+b[x],x));}
    if(op==1){q1.push(mp(a[x],x));q4.push(mp(-b[x],x));}
    if(op==2){q2.push(mp(-a[x],x));q3.push(mp(b[x],x));}
    if(op==3){q6.push(mp(-a[x]-b[x],x));}
}
int main()
{
    //ios::sync_with_stdio(false);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll w4p3r=read();
    while(w4p3r--)
    {
        n=read(),k=read(),l=read();
        while(!q1.empty())q1.pop();
        while(!q2.empty())q2.pop();
        while(!q3.empty())q3.pop();
        while(!q4.empty())q4.pop();
        while(!q5.empty())q5.pop();
        while(!q6.empty())q6.pop();
        q1.push(mp(-inf,0));q2.push(mp(-inf,0));q3.push(mp(-inf,0));q4.push(mp(-inf,0));q5.push(mp(-inf,0));q6.push(mp(-inf,0));
        FOR(i,1,n)a[i]=read();
        FOR(i,1,n)b[i]=read();
        FOR(i,1,n)ans[i]=0;ll answer=0;
        FOR(i,1,n)p[i]=mp(a[i],i);
        sort(p+1,p+n+1);reverse(p+1,p+n+1);
        FOR(i,1,k){answer+=p[i].fr;ans[p[i].sd]|=2;}
        FOR(i,1,n)p[i]=mp(b[i],i);
        sort(p+1,p+n+1);reverse(p+1,p+n+1);
        FOR(i,1,k){answer+=p[i].fr;ans[p[i].sd]|=1;}
        FOR(i,1,n)add(i,ans[i]);
        FOR(i,1,n)l-=(ans[i]==3);l=max(l,0LL);
        //cout<<"WTF:"<<answer<<" "<<l<<endl;
        while(l--)
        {
            while(!q1.empty()){ll x=q1.top().sd;if(!x||ans[x]==1)break;q1.pop();}
            while(!q2.empty()){ll x=q2.top().sd;if(!x||ans[x]==2)break;q2.pop();}
            while(!q3.empty()){ll x=q3.top().sd;if(!x||ans[x]==2)break;q3.pop();}
            while(!q4.empty()){ll x=q4.top().sd;if(!x||ans[x]==1)break;q4.pop();}
            while(!q5.empty()){ll x=q5.top().sd;if(!x||ans[x]==0)break;q5.pop();}
            while(!q6.empty()){ll x=q6.top().sd;if(!x||ans[x]==3)break;q6.pop();}
            ll v1=q1.top().fr,v2=q2.top().fr,v3=q3.top().fr,v4=q4.top().fr,v5=q5.top().fr,v6=q6.top().fr;
            ll t1=v1+v2,t2=v3+v4,t3=v5+v2+v4,t4=v1+v3+v6;
            ll maxn=-inf;
            if(t1>maxn)maxn=t1;if(t2>maxn)maxn=t2;if(t3>maxn)maxn=t3;if(t4>maxn)maxn=t4;
            if(t1==maxn)
            {
                ll x=q1.top().sd,y=q2.top().sd;
                ans[x]=3,ans[y]=0;answer+=a[x]-a[y];
                add(x,ans[x]);add(y,ans[y]);
            }//情况1
            else if(t2==maxn)
            {
                ll x=q3.top().sd,y=q4.top().sd;
                ans[x]=3,ans[y]=0;answer+=b[x]-b[y];
                add(x,ans[x]);add(y,ans[y]);
            }//情况2
            else if(t3==maxn)
            {
                ll x=q5.top().sd,y=q2.top().sd,z=q4.top().sd;
                ans[x]=3;ans[y]=0;ans[z]=0;answer+=a[x]+b[x]-a[y]-b[z];
                add(x,ans[x]);add(y,ans[y]);add(z,ans[z]);
            }//情况3
            else
            {
                ll x=q1.top().sd,y=q3.top().sd,z=q6.top().sd;
                ans[x]=3,ans[y]=3;ans[z]=0;answer+=a[x]+b[y]-(a[z]+b[z]);
                add(x,ans[x]);add(y,ans[y]);add(z,ans[z]);
            }//情况4
        }
        printf("%lld\n",answer);
    }
    return 0;
}
//gl

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq