题解：CF2132E Arithmetics Competition

HPXXZYY · 2025-08-26 10:49:33 · 题解

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

给定两个数组 a_{1 \dots n},b_{1 \dots m} 和 q 次询问。每次询问给定三个参数 x,y,z，你需要求出在 \{ a_{i} \} 中选出不超过 x 个数且在 \{ b_{i} \} 中选出不超过 y 个数的前提下，两个数组一共选出恰好 z 个数的最大的和。

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

首先考虑在没有 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} \}。我们发现，如果

那么在 \{ b_{i} \} 中选择 s 个数是不劣于全部选择权都给 \{ a_{i} \} 的（在这个式子中 a,b 都已经从大到小排序）。

相反的，如果

那么一定不会选 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))。

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;
}