题解：CF2132E Arithmetics Competition

\color{blue}{\texttt{[Problem Discription]}}

不提供题目翻译，仅提供简要题面。

给定两个数组

a_{1 \dots n},b_{1 \dots m}

和

q

次询问。每次询问给定三个参数

x,y,z

，你需要求出在

\{ a_{i} \}

中选出不超过

x

个数且在

\{ b_{i} \}

中选出不超过

y

个数的前提下，两个数组一共选出恰好

z

个数的最大的和。

1 \leq n,m,q \leq 2 \times 10^{5}

。

\color{blue}{\texttt{[Analysis]}}

显然，肯定选最大的那些数答案最优。

首先考虑在没有

x,y

的限制的情况下怎么求解答案。

和归并排序类似的思路，我们把

\{ a_{i} \},\{ b_{i} \}

从大到小排序之后，逐位进行比较，谁打就优先选择谁。这样做是

O(n+m)

的。

可是现在有个数的限制，怎么办？

有一点还是可以确定的，就是如果最终

\{ a_{i} \}

中选择了

z_{1}

个数，

\{ b_{i} \}

中选择了

z_{2}

个数，那么这

z_{1}

个数一定是

\{ a_{i} \}

中最大的

z_{1}

个数。

上面的简单问题的思路可以给我们另外一点启发：我们考虑什么时候会在

\{ b_{i} \}

中选数而不是在

\{ a_{i} \}

选数？其实只有两种情况：

$\{ a_{i} \}$ 中选出来的数的个数已经达到了上界要求。
$\{ b_{i} \}$ 中再选的这个数比 $\{ a_{i} \}$ 中的某个数大，可以用它代替那个数。

所以现在就有这么一种思路：假设我们最开始全部选择

\{ a_{i} \}

中数（先别管超不超上界），现在考虑要把某些选择的机会留给

\{ b_{i} \}

。我们发现，如果

b_{s} \geq a_{z-s+1}

那么在

\{ b_{i} \}

中选择

s

个数是不劣于全部选择权都给

\{ a_{i} \}

的（在这个式子中

a,b

都已经从大到小排序）。

相反的，如果

b_{s}< a_{z-s+1}

那么一定不会选

b_{s}

，因此选

b_{s}

带来的收益不如选

a_{z-s+1}

。

因此满足

b_{s}>a_{z-s+1}

的最大的

s

就是最终答案需要在

b

中选的数的个数。

且随着

s

的增大，左侧在减小，右侧在增大，因此可以二分求出临界的

s

。单次询问是对数的时间复杂度。

总时间复杂度

O(n \log n+m \log m+q \log (n+m))

。

\color{blue}{\text{Code}}

CPP

const int N=2e5+100;
typedef long long ll;
 
int n,m,q,a[N<<1],b[N<<1];
ll prea[N<<1],preb[N<<1];
 
void Regulate(int *a,int n){
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
}
 
int OZDY(){
	n=read();m=read();q=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++)
		b[i]=read();
	
	Regulate(a,n);
	Regulate(b,m);
	
	for(int i=n+1;i<=n+m;i++) a[i]=0;
	for(int i=m+1;i<=n+m;i++) b[i]=0;//记得清空
	
	for(int i=1;i<=n+m;i++)
		prea[i]=prea[i-1]+a[i];
	for(int i=1;i<=n+m;i++)
		preb[i]=preb[i-1]+b[i];
	b[0]=0x3f3f3f3f;//记得把 b[0] 设置成一个很大的数值，原因下面解释 
	
	for(int T=1;T<=q;T++){
		int x=read(),y=read(),z=read();
		x=min(x,min(n,z));y=min(y,min(m,z));
		
		if (z==0){
			printf("0\n");
			continue;
		}
		
		int l=z-x,r=y,res=z-x;
		//假设全选 a，二分让出几个给 b 
		while (l<=r){
			int mid=(l+r)>>1;//如果 l=0,r=1，那么 mid=0，此时如果 b[0] 没有被初始化成一个极大值的话，r=1 是不会被二分考虑到的
			
			if (b[mid]>=a[z-mid+1]){
				res=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		
		if (res>m) printf("%lld\n",preb[m]+prea[z-m]);
		else if (z-res>n) printf("%lld\n",prea[n]+preb[z-n]);
		else printf("%lld\n",preb[res]+prea[z-res]);
	}
	
	return 0;
}
 
int main(){
	int T=read();
	while (T--) OZDY();
	
	return 0;
}

题解：CF2132E Arithmetics Competition

文章操作

相关推荐

评论

题解：CF2132E Arithmetics Competition