题解

将所有物品分成四类,分别为两人共同喜欢的,只有一人喜欢的,没人喜欢的。

首先,先从两人共同喜欢的物品里找出 \(k\) 个,这时,就要从剩余的找出 \(\rm m-k\) 个,而且是最小的。

用一棵权值线段树维护,因为值域太大,所以离散化或动态开点。

之后,指向共同喜欢的物品数量的指针递减,直至 \(0\) 同时增加选取其它物品的量,删除选了的,加上没选的。

因为指针单调递减,所以复杂度为 \(\mathcal O\rm (nlogn)\)

Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define pb(x) push_back(x)
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=2e5+7,INF=1e9;
int v[N],vis1[N],vis2[N],a,b,n,m,k,nm;
ll sum,ans=1e18;
vector<int> lv[3];
inline int cmp(int x,int y) {return v[x]<v[y];}
struct Seg{
#define ls(x) T[x].l
#define rs(x) T[x].r
struct segmenttree{int nm,l,r;ll sum;}T[N<<6];
int st[N<<6],cnt,tot,rt;
inline void up(int x) {
T[x].nm=T[ls(x)].nm+T[rs(x)].nm;
T[x].sum=T[ls(x)].sum+T[rs(x)].sum;
}
inline int New() {return cnt?st[cnt--]:p(tot);}
inline void Del(int &x) {st[p(cnt)]=x;x=0;}
void update(int &x,int p,int l,int r) {
if (!x) x=New();
if (l==r) return (void)(T[x].sum+=p,p(T[x].nm));
int mid(l+r>>1);
if (p<=mid) update(ls(x),p,l,mid);
else update(rs(x),p,mid+1,r);
up(x);
}
void del(int &x,int p,int l,int r) {
if (l==r) {
--T[x].nm,T[x].sum-=p;
if (!T[x].nm) Del(x);
return;
}
int mid(l+r>>1);
if (p<=mid) del(ls(x),p,l,mid);
else del(rs(x),p,mid+1,r);
up(x);
}
ll query(int x,int siz,int l,int r) {
if (!x) return 0;
if (l==r) return (ll)l*(ll)siz;
int mid(l+r>>1);
ll res(0);
if (T[ls(x)].nm>=siz) res+=query(ls(x),siz,l,mid);
else res+=T[ls(x)].sum+query(rs(x),siz-T[ls(x)].nm,mid+1,r);
return res;
}
}T;
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n),read(m),read(k);
if (m<k) {puts("-1");return 0;}
for (ri i(1);i<=n;p(i)) read(v[i]);
read(a);
for (ri i(1),id;i<=a;p(i)) read(id),vis1[id]=1;
read(b);
for (ri i(1),id;i<=b;p(i)) read(id),vis2[id]=1;
for (ri i(1);i<=n;p(i)) {
if (vis1[i]&&vis2[i]) lv[0].pb(i);
else if (vis1[i]) lv[1].pb(i);
else if (vis2[i]) lv[2].pb(i);
else T.update(T.rt,v[i],1,INF);
}
sort(lv[0].begin(),lv[0].end(),cmp);
sort(lv[1].begin(),lv[1].end(),cmp);
sort(lv[2].begin(),lv[2].end(),cmp);
ri bc=cmin((int)lv[0].size(),k),fr=1;
ri siz1=lv[1].size(),siz2=lv[2].size();
if (bc+siz1<k) {puts("-1");return 0;}
if (bc+siz2<k) {puts("-1");return 0;}
for (ri i(0);i<bc;p(i)) sum+=v[lv[0][i]],p(nm);
while(fr+bc<=k) sum+=v[lv[1][fr-1]],sum+=v[lv[2][fr-1]],nm+=2,p(fr);
for (ri i(fr);i<=siz1;p(i)) T.update(T.rt,v[lv[1][i-1]],1,INF);
for (ri i(fr);i<=siz2;p(i)) T.update(T.rt,v[lv[2][i-1]],1,INF);
if (nm>m) {puts("-1");return 0;}
ans=cmin(ans,sum+T.query(T.rt,m-nm,1,INF));
bc-=1,nm-=1;
if (bc>=0) T.update(T.rt,v[lv[0][bc]],1,INF),sum-=v[lv[0][bc]];
while(bc>=0&&bc+siz1>=k&&bc+siz2>=k) {
while(fr+bc<=k) {
sum+=(ll)v[lv[1][fr-1]]+(ll)v[lv[2][fr-1]];
T.del(T.rt,v[lv[1][fr-1]],1,INF);
T.del(T.rt,v[lv[2][fr-1]],1,INF);
nm+=2;
p(fr);
}
if (nm>m) break;
ans=cmin(ans,sum+T.query(T.rt,m-nm,1,INF));
--bc,--nm;
if (bc>=0) T.update(T.rt,v[lv[0][bc]],1,INF),sum-=v[lv[0][bc]];
}
printf("%lld\n",ans);
return 0;
}
}
int main() {return nanfeng::main();}

最新文章

  1. ABP文档 - 通知系统
  2. HTTP协议请求响应过程和HTTPS工作原理
  3. 怎么在js中,访问viewbag,viewdata等等的值
  4. T-SQL编程 —— 用户自定义函数(标量函数)
  5. ubuntu下Qt cannot find -lGL错误的解决方法 (转载)
  6. [R语言画图]气泡图symbols
  7. 在LINUX的命令提示符及CMD命令提示符中显示时间
  8. javascript 精典案例分析一览
  9. old linkedin profile
  10. P2P之UDP穿透NAT的原理与实现
  11. UCOSii项目在NIOSii上的移植
  12. jmeter添加断言
  13. js篇-数组合并其中属性值相同的项目且属性值相加
  14. POI兴趣点搜索 - 地理信息系统(6)
  15. 周强201771010141《面向对象程序设计(java)》第六周学习总结
  16. 十六进制颜色值和rgb颜色值互相转换
  17. 如何在Windows中通过Cygwin来使用Linux命令行
  18. mac 安装 tomcat 配置
  19. DataTable转换成实体
  20. 整合最优雅SSM框架:SpringMVC + Spring + MyBatis 基础

热门文章

  1. centos搭建dns服务器
  2. ROS2学习之旅(14)——编写简单的发布者和订阅者(C++)
  3. Android布局方式总结
  4. Android系统编程入门系列之界面Activity交互响应
  5. Grafana、Prometheus-监控平台
  6. Java基础00-集合进阶26
  7. sql-2-DDL
  8. Python - list 列表常见方法
  9. CF459E-DP
  10. 《手把手教你》系列技巧篇(十一)-java+ selenium自动化测试-元素定位大法之By tag name(详细教程)