D e s c r i p t i o n Description Description 有 n n n个物品，第 i i i个物品代价为 v i v_i vi?
有两个人 A , B A,B A,B，它们各自喜欢 a , b a,b a,b个物品，分别是 a i , b i a_i,b_i ai?,bi?
要求从中选出 m m m个物品，满足至少有 k k k个 A A A喜欢的，至少有 k k k个 B B B喜欢的
求最小代价和
数据范围： n ≤ 2 × 1 0 5 n\leq 2\times 10^5 n≤2×105
S o l u t i o n Solution Solution 设 G G G表示两人共同喜欢的物品构成的集合
用 A , B A,B A,B分别表示只有 A / B A/B A/B喜欢物品的集合（代码中用了 o n l y only only表示）
将 C C C表示 A , B A,B A,B都不喜欢的集合，显然 G , A , B , C G,A,B,C G,A,B,C从小到大取是更优的
枚举一个数 i i i，表示从 G G G集合中选取的个数
接着从 A A A集合中，选出 k ? i k-i k?i个数
从 B B B集合中，选出 k ? i k-i k?i个数
那么我们此时还需要选 z = m ? ( k ? i ) ? ( k ? i ) ? i = m ? 2 k + i z=m-(k-i)-(k-i)-i=m-2k+i z=m?(k?i)?(k?i)?i=m?2k+i个数
那么这些数都包括哪些呢？
包括集合 C C C以及集合 A , B A,B A,B中没有选取的
那么我们把集合 A , B A,B A,B中没有选取的，都当做是集合 C C C中的元素
现在，我们就要在集合 C C C中选出 z z z个最小的数，补齐数量即可
也就是说，我们需要写一种支持每次加入一个数，查询前 z z z大的数的和的数据结构
【贪心|nssl 1477.赛】可以用离散化+【权值线段树/（二分+树状数组）】解决，也可以用对顶堆解决，这里只讲后者。
把集合 C C C放入一个小根堆中（这里的集合 C C C包括 A , B A,B A,B中没有选取的），记为 q 1 q_1 q1?
前面的选取，我们直接找到 A , B A,B A,B都不喜欢的放入，中间由于 i i i我们是从小到大枚举的，所以 k ? i k-i k?i在慢慢变小，从 A , B A,B A,B中选择的元素会越来越少，踢出来的会越来越多，但是每次最多只会各多一个
我们只需要把踢出的这些元素放入 q 1 q_1 q1?即可
后面补齐 z z z的部分，我们建立一个大根堆 q 2 q_2 q2?，满足其堆顶小于 q 1 q_1 q1?的堆顶（也就是 q 2 q_2 q2?中最大的比 q 1 q_1 q1?中最小的还小）如果控制 q 2 q_2 q2?的大小为 z z z（即长度不够时，从 q 1 q_1 q1?中拿元素去补），那么它里面元素的和就是这一部分的答案
最后总结一遍答案的计算过程
s u m sum sum：选取 A , B A,B A,B共同喜欢元素的和，直接求和即可
s u m a suma suma：只有 A A A喜欢元素的和，直接计算，每当踢出一个元素，要减去
s u m b sumb sumb：和上面同理
s u m 0 sum0 sum0：表示我们已经选取了 i i i个共同的，各取了 k ? i k-i k?i个两人喜欢的，剩下 z z z个选取的和（即 q 2 q_2 q2?中元素的和），如果 q 2 q_2 q2?的元素不足 k k k个，则从 q 1 q_1 q1?中选取元素放入 q 2 q_2 q2?中直到 q 2 q_2 q2?恰好有 z z z个元素，此时这 z z z个元素就是原 q 1 q_1 q1?中的前 z z z小值，同时，记得维护 q 1 q_1 q1?的堆顶小于 q 2 q_2 q2?的堆顶，否则交换它们的堆顶直到合法为止，这个过程也要维护 s u m 0 sum0 sum0
最终答案 A n s = m i n { s u m + s u m a + s u m b + s u m 0 } Ans=min\{sum+suma+sumb+sum0\} Ans=min{sum+suma+sumb+sum0}
时间复杂度：由于每个物品入堆出堆的次数是 n n n级别的，所以总的复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
C o d e Code Code

#include #include #include #include #define LL long long using namespace std; int n,m,k,a,b,x,z; LL sum0,suma,sumb,sum,ans=1e18,gt[200010],onlya[200010],onlyb[200010],v[200010]; bool rea[200010],reb[200010]; priority_queueq1,q2; inline LL read() { char c; LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1; f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } signed main() { n=read(); m=read(); k=read(); for(register int i=1; i<=n; i++) v[i]=read(); a=read(); for(register int i=1; i<=a; i++) x=read(),rea[x]=true; b=read(); for(register int i=1; i<=b; i++) x=read(),reb[x]=true; for(register int i=1; i<=n; i++) if(rea[i]&&reb[i]) gt[++gt[0]]=v[i]; else if(rea[i]) onlya[++onlya[0]]=v[i],suma+=v[i]; //维护suma else if(reb[i]) onlyb[++onlyb[0]]=v[i],sumb+=v[i]; //维护sumb else q1.push(-v[i]); //两个都不喜欢的，放入待选集合 sort(gt+1,gt+1+gt[0]); sort(onlya+1,onlya+1+onlya[0]); sort(onlyb+1,onlyb+1+onlyb[0]); for(register int i=0; i<=min(gt[0],(long long)k); i++) { if(i>0) sum+=gt[i]; while(onlya[0]>k-i) { suma-=onlya[onlya[0]]; q1.push(-onlya[onlya[0]]); //A不选取的，放入待选集合 onlya[0]--; } while(onlyb[0]>k-i) { sumb-=onlyb[onlyb[0]]; q1.push(-onlyb[onlyb[0]]); //B不选取的，放入待选集合 onlyb[0]--; } z=m-onlya[0]-onlyb[0]-i; if(z<0) continue; //不需要补齐(说明此时选的数量过了，是不合法的，必须要恰好m个元素) if(onlya[0]!=k-i||onlyb[0]!=k-i) continue; //如果物品没有选够，也是不合法的 while(q1.size()&&(q2.size()