题目

传送门

题解

记总物品数为 \(n\)，只能买 \(m\) 个使得两人喜欢的分别至少有 \(k\) 个。

记 \(sz1\) 为两人都喜欢的商品数，\(sz2,sz3\) 分别为 \(A,B\) 各自喜欢的商品数，首先我们可以预处理出来这仨东西：

inline bool cmp(const int i,const int j){
    if(i==-1)return 0;
    if(j==-1)return 1;
    return c[i]<c[j];
}

int vis[MAXN+5];
inline void Solvetype(){
    rep(i,1,sz2)vis[a[i]]=1;
    rep(i,1,sz3)if(vis[b[i]]==1)
        vis[b[i]]=-1,both[++sz1]=b[i];
    rep(i,1,sz2)if(vis[a[i]]==-1)a[i]=-1;
    rep(i,1,sz3)if(vis[b[i]]==-1)b[i]=-1;
    sort(a+1,a+sz2+1,cmp),sort(b+1,b+sz3+1,cmp),sort(both+1,both+sz1+1,cmp);
    sz2-=sz1,sz3-=sz1;
}

考虑无解的情况：

1. \(m<k\) 显然无解；
2. 即使两人买最少商品也超过 \(m\)，即 \(m<sz1+2\times (k-sz1)\)；
3. 两个人喜欢的商品数没有 \(k\) 个，即 \(sz1+sz2<k\) 或者 \(sz1+sz3<k\)；

然后，我们考虑枚举我们一共买了 \(x\) 个两人都喜欢的商品，然后每个人一定还需买 \(sz1-x,sz2-x\) 个各自喜欢的，贪心地，我们一定都是从小往大买

然后，我们在剩下没买的商品中选择前 \(m-x-(sz1-x)-(sz2-x)\) 小的并将其买下，此处我们可以使用线段树（同机房有人用更巧妙的数组来做，但是时间复杂度依然要带 \(\log\)）维护全部商品中没选的的商品和，然后在线段树中找前 \(m-x-(sz1-x)-(sz2-x)\) 小即可

总体来说题并不复杂，但是可以是因为我方法的原因，实现较为麻烦

总时间复杂度为 \(\mathcal O(k\log n+n\log n)\)

代码

#include<bits/stdc++.h>
using namespace std;

#define rep(i,__l,__r) for(signed i=(__l),i##_end_=(__r);i<=i##_end_;++i)
#define fep(i,__l,__r) for(signed i=(__l),i##_end_=(__r);i>=i##_end_;--i)
#define erep(i,u) for(signed i=tail[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
#define writc(a,b) fwrit(a),putchar(b)
#define mp(a,b) make_pair(a,b)
#define ft first
#define sd second
typedef long long LL;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef unsigned uint;
#define Endl putchar('\n')
// #define int long long
// #define int unsigned
// #define int unsigned long long
#define int long long

#define cg (c=getchar())
template<class T>inline void qread(T& x){
    char c;bool f=0;
    while(cg<'0'||'9'<c)f|=(c=='-');
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    if(f)x=-x;
}
template<class T>inline T qread(const T sample){
    T x=0;char c;bool f=0;
    while(cg<'0'||'9'<c)f|=(c=='-');
    for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
    return f?-x:x;
}
template<class T>void fwrit(const T x){//just short,int and long long
    if(x<0)return (void)(putchar('-'),fwrit(-x));
    if(x>9)fwrit(x/10);
    putchar(x%10^48);
}
template<class T>inline T Max(const T x,const T y){return x>y?x:y;}
template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
template<class T>inline T fab(const T x){return x>0?x:-x;}
inline int gcd(const int a,const int b){return b?gcd(b,a%b):a;}
inline void getInv(int inv[],const int lim,const int MOD){
    inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
}
inline LL mulMod(const LL a,const LL b,const LL mod){//long long multiplie_mod
    return ((a*b-(LL)((long double)a/mod*b+1e-8)*mod)%mod+mod)%mod;
}

const int MAXN=2e5;

int c[MAXN+5];

int both[MAXN+5],sz1;//两个都喜欢的
int a[MAXN+5],sz2;//只有小 A
int b[MAXN+5],sz3;//只有小 B

int n,m,k;

inline void Init(){
    scanf("%lld %lld %lld",&n,&m,&k);
    for(int i=1;i<=n;++i)scanf("%lld",&c[i]);
    scanf("%lld",&sz2);
    for(int i=1;i<=sz2;++i)scanf("%lld",&a[i]);
    scanf("%lld",&sz3);
    for(int i=1;i<=sz3;++i)scanf("%lld",&b[i]);
}

inline bool cmp(const int i,const int j){
    if(i==-1)return 0;
    if(j==-1)return 1;
    return c[i]<c[j];
}

int vis[MAXN+5];
inline void Solvetype(){
    rep(i,1,sz2)vis[a[i]]=1;
    rep(i,1,sz3)if(vis[b[i]]==1)
        vis[b[i]]=-1,both[++sz1]=b[i];
    rep(i,1,sz2)if(vis[a[i]]==-1)a[i]=-1;
    rep(i,1,sz3)if(vis[b[i]]==-1)b[i]=-1;
    sort(a+1,a+sz2+1,cmp),sort(b+1,b+sz3+1,cmp),sort(both+1,both+sz1+1,cmp);
    sz2-=sz1,sz3-=sz1;
    //printf("both:");
    //for(int i=1;i<=sz1;++i)printf("%d ",both[i]);
    //Endl;
    //printf("a:");
    //for(int i=1;i<=sz2;++i)printf("%d ",a[i]);
    //putchar('\n');
    //printf("b:");
    //for(int i=1;i<=sz3;++i)printf("%d ",b[i]);
    //putchar('\n');
}

inline bool cmp2(const int i,const int j){return c[i]<c[j];}

int pointer[MAXN+5],t[MAXN+5];
//pointer : 指向货品 i 在线段树上的点编号
//t : 下标排序

bool exist[MAXN+5];//这个点在线段树上是否存在

int w[MAXN<<2|2],sz[MAXN<<2|2];
#define lc (i<<1)
#define rc (i<<1|1)
#define mid ((l+r)>>1)
#define _lq lc,l,mid
#define _rq rc,mid+1,r
inline void pushup(const int i){
    w[i]=w[lc]+w[rc],sz[i]=sz[lc]+sz[rc];
}
void buildtre(const int i=1,const int l=1,const int r=n){
    //printf("Now is node %d, [%d, %d]\n",i,l,r);
    if(l==r){
        if(!exist[l])sz[i]=w[i]=0;
        else sz[i]=1,w[i]=c[t[l]];
        //printf("node %d is a leaf, sz == %d, w == %d\n",i,sz[i],w[i]);
        return;
    }
    buildtre(_lq),buildtre(_rq);
    pushup(i);
    //printf("node %d(%d, %d), after build, sz == %d, w == %d\n",i,l,r,sz[i],w[i]);
}
void add(const int p,const int x,const int i=1,const int l=1,const int r=n){
    //printf("add:>p == %d, x == %d, (%d, %d, %d)\n",p,x,i,l,r);
    if(l==r){
        sz[i]=x,w[i]=x*c[t[l]];
        //printf("leaf:>after add, sz == %d, w == %d\n",sz[i],w[i]);
        return;
    }
    if(p<=mid)add(p,x,_lq);
    else add(p,x,_rq);
    pushup(i);
    //printf("node %d(%d, %d), after add, sz == %d, w == %d\n",i,l,r,sz[i],w[i]);
}
int queryPre(const int kth,const int i=1,const int l=1,const int r=n){
    if(kth==0)return 0;
    if(l==r)return w[i];
    if(sz[lc]>=kth)return queryPre(kth,_lq);
    return w[lc]+queryPre(kth-sz[lc],_rq);
}

int cost,cntc,base;//计算总共花费以及买了多少个
int ans=0x3f3f3f3f;//最终的答案

inline void Buildtre(){
    for(int i=1;i<=n;++i)t[i]=i;
    sort(t+1,t+n+1,cmp2);
    memset(exist,true,sizeof exist);
    rep(i,1,n)pointer[t[i]]=i;
    //printf("at first, buy %d both\n",min(sz1,k));
    rep(i,1,min(sz1,k)){//初始化买所有的两人都喜欢的
        //printf("buy thing %d\n",both[i]);
        exist[pointer[both[i]]]=false;
        ++cntc;
        cost+=c[both[i]];
    }
    rep(i,1,k-min(sz1,k)){//再买上剩下的一些，让两个人凑足 k 个喜欢的
        //printf("buy thing %d and %d\n",a[i],b[i]);
        exist[pointer[a[i]]]=false;
        exist[pointer[b[i]]]=false;
        cntc+=2;
        cost+=c[a[i]]+c[b[i]];
    }
    //printf("pointer:");
    //rep(i,1,n)writc(pointer[i],' ');Endl;
    //printf("exist:");
    //rep(i,1,n)writc(exist[i],' ');Endl;
    buildtre();
    //printf("after all, cost == %d\n",cost);
    //printf("buy the cheapest %d, their cost is %d\n",m-cntc,queryPre(m-cntc));
    base=cost;
    cost+=queryPre(m-cntc);
    //printf("at beginning:");
    //writc(cost,'\n');
}

signed main(){
    Init();//输入
    Solvetype();//得到都喜欢的以及两个人分别单独喜欢的
    //先特判无解
    if(m<k || sz1+sz2<k || sz1+sz3<k || m<sz1+2*(k-sz1))return !printf("-1\n");
    Buildtre();//初始化
    ans=cost;
    int p=k-min(sz1,k);
    for(int i=min(sz1,k)-1;i>=0 && p<sz2 && p<sz3 && cntc<m;--i){
        add(pointer[both[i+1]],1);//少买一个两人都喜欢的
        base-=c[both[i+1]];
        //printf("do not buy %d, and update cost to %d\n",both[i+1],cost);
        ++p;
        add(pointer[a[p]],0);//每人多买一个自己喜欢的
        add(pointer[b[p]],0);
        base+=c[a[k-i]]+c[b[k-i]];
        //printf("buy %d and %d, and cost is %d\n",a[p],b[p],cost);
        ++cntc;
        //printf("and buy cheapest %d, their cost is %d\n",m-cntc,queryPre(m-cntc));
        cost=base+queryPre(m-cntc);//再找一些剩下的最便宜的补满
        ans=min(ans,cost);
    }
    writc(ans,'\n');
    return 0;
}
/*
10 8 5
3 6 8 5 6 14 16 8 20 17
6
1 2 4 5 8 9
6
2 4 6 7 8 9

ans=66

-----------------------

10 8 9
12 2 7 2 4 1 20 19 1 5
10
3 10 1 6 7 5 8 2 4 9
10
6 9 3 8 5 10 2 7 4 1
ans=-1

-----------------------

6 4 2
1 2 3 4 5 1000
3
1 2 6
3
4 5 6

ans=12
*/