玲珑 2018-03-04
题意:有n个物品,小A和小B各自喜欢其中的某些物品,一件物品可能既被小A喜欢又被小B喜欢,也可能既不被小A喜欢又不被小B喜欢。每个物品都有一个价格$c_i$,让你选出其中的m件物品,满足小A和小B都至少喜欢其中的k件,且总价格最小。
$n\le 2\times 10^5,c_i\le 10^9$
题解:我们把物品分成四部分:0,A,B,AB,并分别排序,然后我们枚举AB中选了i个。接着我们可以二分:在A,B,0中选择的价格最大的物品的价格mid,假设A中有a个数小于等于mid,则我们要从中选max(a,k)个,同理B中选max(b,k)个,C中选m-i-max(a,k)-max(b,k)个。发现这个显然是可以二分的。如果把二分放到线段树上的话,则时间复杂度是$O(n\log n)$。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define lson x<<1 #define rson x<<1|1 using namespace std; typedef long long ll; const int maxn=200010; ll ans; int n,m,k,na,nb,nc,nd,N; int A[maxn],B[maxn],C[maxn],D[maxn],v[maxn],tag[maxn],p[maxn]; int ca[maxn<<2],cb[maxn<<2],cd[maxn<<2],ta[maxn],tb[maxn],td[maxn]; ll sa[maxn],sb[maxn],sd[maxn],ref[maxn]; bool cmp(const int &a,const int &b) { return v[a]<v[b]; } void insert(int l,int r,int x,int a,int b,int c) { if(c==0) ca[x]=b; if(c==1) cb[x]=b; if(c==2) cd[x]=b; if(l==r) return ; int mid=(l+r)>>1; if(a<=mid) insert(l,mid,lson,a,b,c); else insert(mid+1,r,rson,a,b,c); } ll query(int l,int r,int x,int a) { if(l==r) return sa[max(ca[x],a)]+sb[max(cb[x],a)]+sd[cd[x]]-ref[l]*(max(ca[x],a)+max(cb[x],a)+cd[x]+k-a-m); int mid=(l+r)>>1,t=max(ca[lson],a)+max(cb[lson],a)+cd[lson]+k-a; if(t>=m) return query(l,mid,lson,a); return query(mid+1,r,rson,a); } void build(int l,int r,int x) { if(l==r) { ca[x]=ta[l],cb[x]=tb[l],cd[x]=td[l]; return ; } int mid=(l+r)>>1; build(l,mid,lson),build(mid+1,r,rson); ca[x]=ca[rson],cb[x]=cb[rson],cd[x]=cd[rson]; } inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar(); return ret*f; } int main() { n=rd(),m=rd(),k=rd(); int i,a,b; for(i=1;i<=n;i++) v[i]=rd(),p[i]=i; sort(p+1,p+n+1,cmp); for(i=1;i<=n;i++) { if(i==1||v[p[i]]>ref[N]) ref[++N]=v[p[i]]; v[p[i]]=N; } a=rd(); for(i=1;i<=a;i++) b=rd(),tag[b]|=1; a=rd(); for(i=1;i<=a;i++) b=rd(),tag[b]|=2; for(i=1;i<=n;i++) { if(tag[i]==0) D[++nd]=ref[v[i]],td[v[i]]++; if(tag[i]==1) A[++na]=ref[v[i]],ta[v[i]]++; if(tag[i]==2) B[++nb]=ref[v[i]],tb[v[i]]++; if(tag[i]==3) C[++nc]=ref[v[i]]; } sort(A+1,A+na+1),sort(B+1,B+nb+1),sort(C+1,C+nc+1),sort(D+1,D+nd+1); for(i=1;i<=N;i++) ta[i]+=ta[i-1],tb[i]+=tb[i-1],td[i]+=td[i-1]; for(i=1;i<=na;i++) sa[i]=sa[i-1]+A[i]; for(i=1;i<=nb;i++) sb[i]=sb[i-1]+B[i]; for(i=1;i<=nd;i++) sd[i]=sd[i-1]+D[i]; ll sum=0; ans=1ll<<60; build(0,N,1); for(i=0;i<=min(nc,m);i++) { sum+=C[i]; if(min(na,nb)>=k-i&&2*k-i<=m&&i+na+nb+nd>=m) ans=min(ans,sum+query(0,N,1,k-i)); } if(ans==1ll<<60) puts("-1"); else printf("%lld",ans); return 0; }