题解 CF730I 【Olympiad in Programming and Sports】

lndjy · 2021-01-30 07:57:02 · 题解

首先，如果运动团队的人已经确定了，编程团队只要取剩下的大的就好了。

那么我们可以先把最大的 p 个丢到编程团队，然后通过反悔贪心，每次让一个人进入运动团队，一共 s 次。

有两种情况：

1. 将一个没选过的人直接进入运动团队，价值 b_i。
2. 将一个选过的人进入运动团队，再找一个人进入编程团队，价值 b_i-a_i+a_j。

用 3 个堆维护 a_i,b_i,b_i-a_i 每次取最大值。

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N=3e3+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;
}
priority_queue<node,vector<node>,greater<node> > q1,q2,q3;
int op[N],ans,n,p,s;
int main()
{
    cin>>n>>p>>s;
    for(int i=1;i<=n;i++)
    cin>>a[i].num,a[i].id=i;
    for(int i=1;i<=n;i++)
    cin>>b[i].num,b[i].id=i;
    sort(a+1,a+n+1);
    for(int i=1;i<=p;i++)
    op[a[i].id]=1,ans+=a[i].num;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        q1.push(node(i,a[i].num));
        q2.push(node(i,b[i].num));
        q3.push(node(i,b[i].num-a[i].num));
    }
    for(int zwz=1;zwz<=s;zwz++)
    {
        int now=-1e9,i,j,opt;
        while(!q2.empty()&&op[q2.top().id]!=0) q2.pop();
        if(!q2.empty())
        {
            if(q2.top().num>now)
            {
                now=q2.top().num;
                i=q2.top().id;
                opt=1;
            }
        }
        while(!q3.empty()&&op[q3.top().id]!=1) q3.pop();
        while(!q1.empty()&&op[q1.top().id]!=0) q1.pop();
        if(!q1.empty()&&!q3.empty())
        {
            int sum=q1.top().num+q3.top().num;
            if(sum>now)
            {
                now=sum;
                i=q3.top().id;
                j=q1.top().id;
                opt=2;
            }
        }
        ans+=now;
        if(opt==1)
        {
            q2.pop();
            op[i]=2;
        }
        else
        {
            q1.pop();q3.pop();
            op[i]=2;
            op[j]=1;
            q3.push(node(j,b[j].num-a[j].num));
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
    if(op[i]==1)
    cout<<i<<" ";
    cout<<endl;
    for(int i=1;i<=n;i++)
    if(op[i]==2)
    cout<<i<<" "; 
    return 0;
}