CF1998C Perform Operations to Maximize Score

传送门

Solution

取出的 $a_i$ 若 $i>\lfloor \dfrac{n}{2} \rfloor$，则 $\text{median}(c_i)=a_{\lfloor \frac{n}{2} \rfloor}$。否则 $\text{median}(c_i)=a_{\lfloor \frac{n}{2} \rfloor + 1}$。

已知答案为 $a_i+\text{median}(c_i)$，有两种想法：

1. 取 $b_i=1$ 的 $a_i$，然后将 $k$ 全部加在 $a_i$ 上。
2. 取 $b_i=0$ 的 $a_i$，然后将 $k$ 加在其他 $a_i$ 上，使 $\text{median}(c_i)$ 最大化。

易证没有其它更优的方案。

第一条容易计算。第二条可以二分答案 $x$，判断能否通过 $k$ 次操作使得 $\text{median}(c_i)\ge x$。

时间复杂度 $O(n\log n\log a_i)$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 2e5 + 10;

ll n, k, ans, T, c[N];
struct Node {
    ll x, y;
    friend bool operator < (const Node &a, const Node &b) {
        return a.x < b.x;
    }
} a[N];

bool check(ll x)
{
    ll kk = k;
    for (int i = 1; i <= n; i++) 
        c[i] = a[i].x;
    for (int i = n - 1; i; i--)
        if (c[i] < x && kk - (x - c[i]) >= 0 && a[i].y) {
            kk -= x - c[i];
            c[i] = x;
        }
    sort(c + 1, c + 1 + n);
    return c[n / 2] >= x;
}

void solve()
{
    scanf("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i].x);
    ll x = 1e9;
    for (int i = 1; i <= n; i++) 
        scanf("%lld", &a[i].y);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++)
        if (a[i].y == 1)
            x = i;
    if (x == 1e9) {
        printf("%lld\n", a[n].x + a[n / 2].x);
        return;
    }
    if (x > n / 2)
        ans = a[x].x + k + a[n / 2].x;
    else 
        ans = a[x].x + k + a[n / 2 + 1].x;
    ll l = a[n / 2].x, r = 2e10, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            ans = max(ans, a[n].x + mid);
            l = mid + 1;
        } else
            r = mid - 1;
    }
    printf("%lld\n", ans);
}

int main()
{
    scanf("%lld", &T);
    while (T--) solve();
    return 0;
}