P5470 【[NOI2019] 序列】做题记录/题解

lndjy · 2021-01-24 21:35:08 · 题解

首先，假设 l 个公共部分已经确定了，显然直接选 k-l 个最大的就是最优的。

那么我们把 k 个都先按照大的选，然后通过反悔贪心，每一步让公共部分多一个，直到变成 l 个，这样就是最优的。

考虑几种操作能让公共部分多一个。

1. 找一个选了的 a_i，和一个选了的 b_j，然后用 b_i 代替 b_j，代价是 b_i-b_j。
2. 找一个选了的 b_i，和一个选了的 a_j，然后用 a_i 代替 a_j，代价是 a_i-a_j。
3. 找一个选了的 a_i 和 b_j，再找一个没选的位置 k，选 a_k 和 b_k 代替 a_i 和 b_j，代价是 a_k+b_k-a_i-b_j。
4. 找一个选了的 a_i 和 b_j，再找一个都选的位置 k，选 a_j 和 b_i 代替 a_k 和 b_k，代价是 a_j+b_i-a_k-b_k。

拆一下上面的式子，用 6 个堆维护 a_i,-a_i,b_i,-b_i,a_i+b_i,-a_i-b_i。比 CF436E 还恶心。

反悔贪心练习题单qwq

又臭又长的代码（附带第一个测试点数据）

#include<iostream>
#include<cstdio> 
#include<queue>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
const int N=2e5+5;
struct node
{
    int id,num;
    node(int x=0,int y=0)
    {
        id=x;
        num=y;
    }
    bool operator <(const node &p)
    const{
        return num>p.num;
    }
    bool operator >(const node &p)
    const{
        return num<p.num;
    }
}a[N],b[N];
bool cmp(node x,node y)
{
    return x.id<y.id;
}
int n,l,K,op[N];
priority_queue<node,vector<node>,greater<node> > q1,q2,q3,q4,q5,q6;
int ans;
void clear()
{
    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();
    memset(op,0,sizeof op);
    ans=0;
}
void solve()
{
    n=read();K=read();l=read();
    for(int i=1;i<=n;i++)
    a[i].num=read(),a[i].id=i;
    for(int i=1;i<=n;i++)
    b[i].num=read(),b[i].id=i;
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=K;i++)
    ans+=a[i].num,op[a[i].id]++;
    for(int i=1;i<=K;i++)
    ans+=b[i].num,op[b[i].id]+=2;
    int cnt=0;
    for(int i=1;i<=n;i++)
    if(op[i]==3) cnt++;
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);    
    for(int i=1;i<=n;i++)
    {
        q1.push(node(i,a[i].num));
        q2.push(node(i,-a[i].num));
        q3.push(node(i,b[i].num));
        q4.push(node(i,-b[i].num));
        q5.push(node(i,a[i].num+b[i].num));
        q6.push(node(i,-a[i].num-b[i].num));
    }
//  for(int i=1;i<=n;i++)
//  cout<<op[i];
//  cout<<endl;
    for(int zwz=1;zwz<=l-cnt;zwz++)
    {
    //  cout<<zwz<<endl;
        int now=-1e15,opt=0,i=0,j=0,k=0;
    //  cout<<q3.size()<<endl;
        while(!q3.empty()&&op[q3.top().id]!=1) q3.pop();
        while(!q4.empty()&&op[q4.top().id]!=2) q4.pop();
        if(!q3.empty()&&!q4.empty())
        {
            int sum=b[q3.top().id].num-b[q4.top().id].num;
            if(sum>now)
            {
                now=sum;
                i=q3.top().id;
                j=q4.top().id;
                opt=1;
            }
        }
        while(!q1.empty()&&op[q1.top().id]!=2) q1.pop();
        while(!q2.empty()&&op[q2.top().id]!=1) q2.pop();
        if(!q1.empty()&&!q2.empty())
        {
            int sum=a[q1.top().id].num-a[q2.top().id].num;
            if(sum>now)
            {
                now=sum;
                i=q1.top().id;
                j=q2.top().id;
                opt=2;
            }
        }
    //  cout<<zwz<<endl;
        while(!q5.empty()&&op[q5.top().id]!=0) q5.pop();
        while(!q2.empty()&&op[q2.top().id]!=1) q2.pop();
        while(!q4.empty()&&op[q4.top().id]!=2) q4.pop();
        if(!q5.empty()&&!q4.empty()&&!q2.empty())
        {
            int sum=a[q5.top().id].num+b[q5.top().id].num-a[q2.top().id].num-b[q4.top().id].num;
            if(sum>now)
            {
                now=sum;
                i=q2.top().id;
                j=q4.top().id;
                k=q5.top().id;
                opt=3;
            }
        }
    //  cout<<zwz<<endl;
        while(!q6.empty()&&op[q6.top().id]!=3) q6.pop();
        while(!q1.empty()&&op[q1.top().id]!=2) q1.pop();
        while(!q3.empty()&&op[q3.top().id]!=1) q3.pop();
        if(!q6.empty()&&!q3.empty()&&!q1.empty())
        {
            int sum=a[q1.top().id].num+b[q3.top().id].num-a[q6.top().id].num-b[q6.top().id].num;
            if(sum>now)
            {
                now=sum;
                i=q3.top().id;
                j=q1.top().id;
                k=q6.top().id;
                opt=4;
            }
        }
    //  cout<<zwz<<endl;
        ans+=now;
    //  cout<<now<<" "<<opt<<endl;
    //  cout<<i<<" "<<j<<" "<<k<<endl;
        if(opt==1)
        {
            op[i]=3;
            op[j]=0;
            //cout<<q3.size()<<endl;
            q3.pop();q4.pop();
        //  cout<<q3.size()<<endl;
            q6.push(node(i,-a[i].num-b[i].num));
            q5.push(node(j,a[j].num+b[j].num));
        }
        else if(opt==2)
        {
            op[i]=3;
            op[j]=0;
            q1.pop();q2.pop();
            q6.push(node(i,-a[i].num-b[i].num));
            q5.push(node(j,a[j].num+b[j].num));         
        }
        else if(opt==3)
        {
            op[k]=3;
            op[i]=op[j]=0;
            q2.pop();q4.pop();q5.pop();
            q6.push(node(k,-a[k].num-b[k].num));
            q5.push(node(i,a[i].num+b[i].num));
            q5.push(node(j,a[j].num+b[j].num));
        }
        else
        {
            op[k]=0;
            op[i]=op[j]=3;
            q1.pop();q3.pop();q6.pop();
            q6.push(node(i,-a[i].num-b[i].num));
            q6.push(node(j,-a[j].num-b[j].num));
            q5.push(node(k,a[k].num+b[k].num));
        }
    //  cout<<q3.size()<<endl;
    //  system("pause");
    }
    cout<<ans<<endl;
}
signed main()
{
    int T=read();
    while(T--)
    {
        clear();
        solve();
    }
    return 0;
}
/*
10
5 2 1
965603156 594151484 137421888 511721918 163053182
239833925 530765178 939584446 407283748 456390712
6 3 1
563597651 744310197 650756091 459159791 905965537 501095539
436402349 255689803 349243909 650771685 210810349 498904461
5 2 1
22583989 839924760 708231676 112954530 76654839
903218601 411750909 214760058 460569766 162867801
3 1 1
152517359 551481336 649305529
141934634 773929513 350494617
6 3 1
464020128 779739924 684448073 705217786 801717091 157102288
568955227 245753356 441864136 294782214 313154002 935222153
1 1 1
699242980
459838444
7 4 1
887100126 373954728 331917628 425297229 570948801 702368573 545916379
143951398 675892241 674371136 619857308 429051199 297631427 454083621
5 2 2
40869605 220229669 66179050 924234004 522215952
547926918 283456228 534215193 131503240 145556018
3 1 1
746003558 889997254 514823835
318446236 133597131 526467792
4 2 2
946692615 576958060 193743104 148410523
939939583 524058103 475154057 418784570

*/
/*
3030104264
3799951880
2863125946
1325410849
4211946604
1159081424
5130538185
1723509214
1064449794
2987648361
*/