【CF799E】Aquarium decoration

题意：有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;

}

巴特西

【CF799E】Aquarium decoration 线段树

【CF799E】Aquarium decoration

最新文章

热门文章