贪心、二分

赛时想出数个假做法并且在比赛结束前想到真做法但没写出来就结束了，写这个笔记的时候又忘了真做法。

给定长度为 $n$ 的序列 $a$ 和 $\texttt{01}$ 序列 $b$，同时能执行至多 $k$ 次操作，每次操作能够选定一个满足 $b_i=1$ 的整数 $i$，使得 $a_i \leftarrow a_i+1$。最大化 $\max\limits_{i=1}^{n} (a_i + \operatorname{median}(c_i))$ 的值，其中序列 $c_i$ 是序列 $a$ 删除 $a_i$ 后得到的序列，$\operatorname{median}(c_i)$ 是指序列 $c_i$ 中第 $\left\lfloor \dfrac{n}{2} \right\rfloor$ 小的数。

枚举 $1 \sim n$ 并计算答案。由于对 $a_i$ 操作一定能让 $a_i$ 变大而不一定能让 $\operatorname{median} (c_i)$ 变大，对于 $b_i = 1$ 的整数 $i$ 直接把 $a_i$ 加上 $k$ 并计算 $\operatorname{median}(c_i)$ 的值。对于 $b_i = 0$ 的整数 $i$，由于没法动 $a_i$ 了，考虑如何操作序列能最大化贡献，以及如何计算 $\operatorname{median}(c_i)$。

考虑二分答案，对于给定值 $mid$ 而言，如果能够让序列中不小于它的数的数量不低于 $\left\lfloor \dfrac{n+1}{2} \right\rfloor$ 个则 $mid$ 能够成为 $\operatorname{median}(c_i)$。不小于 $mid$ 且 $b_i=0$ 的元素数量能够二分得到（注意当前被去掉的 $a_i$ 不能计入），假设这样的 $a_i$ 有 $w_0$ 个，就需要让 $\left\lfloor \dfrac{n+1}{2} \right\rfloor - w_0$ 个 $b_i = 1$ 的元素的值不小于 $mid$。

二分出不小于 $mid$ 且 $b_i=1$ 的元素数量，设其为 $w_1$，现在需要通过操作让 $\left\lfloor \dfrac{n+1}{2} \right\rfloor - w_0 -w_1$ 个原本小于 $mid$ 的数不小于 $mid$，二分出小于 $mid$ 的前 $\left\lfloor \dfrac{n+1}{2} \right\rfloor - w_0 -w_1$ 个数，使用前缀和判断。注意二分右边界不应小于 $2 \times 10^9$，答案最大为 $3 \times 10^9$。

总体时间复杂度 $O(n \log^2 n)$。

#include<bits/stdc++.h>
using namespace std;
int n,k,cnt[2],a[200'005],b[200'005],c[200'005],w[2][200'005];
long long sum[200'005];
bool fail(int x,int i){
    int res=(n+1)/2;
    if(cnt[0]) res-=cnt[0]-(lower_bound(w[0]+1,w[0]+cnt[0]+1,x)-w[0])+1;
    if(a[i]>=x) ++res;
    if(cnt[1]) res-=cnt[1]-(lower_bound(w[1]+1,w[1]+cnt[1]+1,x)-w[1])+1;
    if(res<=0) return 0;
    int pos=lower_bound(w[1]+1,w[1]+cnt[1]+1,x)-w[1]-1;
    if(pos<res) return 1;
    return sum[pos]-sum[pos-res]+k<1ll*res*x;
}
void solution(){
    cin>>n>>k,cnt[0]=0,cnt[1]=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) w[b[i]][++cnt[b[i]]]=a[i];
    copy(a+1,a+n+1,c+1),sort(c+1,c+n+1);
    sort(w[0]+1,w[0]+cnt[0]+1);
    sort(w[1]+1,w[1]+cnt[1]+1);
    for(int i=1;i<=cnt[1];i++) sum[i]=w[1][i]+sum[i-1];
    unsigned int ans=0u;
    for(int i=1;i<=n;i++){
        if(b[i]){
            if(a[i]<=c[n/2]) ans=max(ans,0u+a[i]+k+c[n/2+1]);
            else ans=max(ans,0u+a[i]+k+c[n/2]);
        }
        else{
            int l=1,r=2'000'000'000,aim=1;
            while(l<=r){
                int mid=l+(r-l)/2;
                if(fail(mid,i)) r=mid-1;
                else aim=mid,l=mid+1;
            }
            ans=max(ans,0u+a[i]+aim);
        }
    }
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}