题解：AT_abc444_f [ABC444F] Half and Median

kaikatandy · 2026-06-08 18:49:08 · 题解

简单题，给出一种大常数，没有脑子的解法。

考虑到将问题转化成“中位数 \ge med 是否可行”，很好解决。因为这个转化为贪心提供了一个基准 med。于是，我们二分 med。

注意到一个数不断进行对半分，最后只会有 \mathcal{O(1)} 个值，比如 7 \to 3,4 \to 1,2,2,2。

那么就可以在 \log V 的时间内，求出一个不小于 med 的数 a 分解出的多重集 S，满足 \sum S = a 且 \forall x \in S,\lfloor \frac{x}{2} \rfloor < med。我们令可重集 T = \biguplus S 。

对于 med，考虑贪心。维护一个 sum，代表 < med 的数之和（意义是最多可以分成多少个数）。先统计一遍 < med 的数个数 cnt_l，如果 cnt_l > \lfloor \frac{n + m}{2} \rfloor，那么显然一定不可行。

从现在开始，一旦出现 |T| < \lceil \frac{n + m}{2} \rceil，那么肯定不可行；一旦出现 |T| + sum \ge n + m，那么肯定可行。前者判定优先。

::::info[贪心] 在以下过程中对 T，sum 进行实时维护。

我们考虑将 T 中的数逐个分解成 < med 的数。由 T 的定义我们知道 \max T \le 2med - 1。

先考虑分解 2med - 1，因为这样不会使 |T| 减小。

然后从大到小，将 T 中的元素依次分解。 ::::

我们使用 map 维护可重集，可以做到 n \log V 的贪心，一共带两只老哥。

::::success[代码，最大点 3975 ms]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
int n, m, a[N];

map<int, int> cal(int x, int lim){
    map<int, int> cur, nxt;
    cur[x] = 1;
    while(1){
        nxt.clear();
        for(auto ss: cur){
            int fs, sn;
            tie(fs, sn) = ss;
            int A = fs / 2, B = fs - A;
            if(A >= lim && B >= lim) nxt[A] += sn, nxt[B] += sn;
            else nxt[fs] += sn;
        }
        if(cur == nxt) break;
        cur = nxt;
    }
    return cur;
}

int CEIL(int x, int y){
    return x / y + (x % y > 0);
}

bool check(int med){

    int len = n + m, req = (len + 1) / 2;

    int cntl = 0;
    for(int i = 1; i <= n; i ++) cntl += (a[i] < med);
    if(cntl >= req) return false;

    int sum = 0, cnt = 0;
    map<int, int> res;
    for(int i = 1; i <= n; i ++){
        if(a[i] < med) sum += a[i];
        else{
            map<int, int> tmp = cal(a[i], med);
            for(auto ss: tmp) res[ss.first] += ss.second, cnt += ss.second;
        }
    }

    if(cnt < req) return false;
    if(cnt + sum >= len) return true;

    if(res.count(med * 2 - 1)){
        int cc = res[med * 2 - 1];
        sum += cc * (med - 1);
        res.erase(med * 2 - 1);
        res[med] += cc;
    }

    if(cnt + sum >= len) return true;

    for(auto it = res.rbegin(); it != res.rend(); it ++){
        int num, app;
        tie(num, app) = (*it);
        if(num == 1) break;
        int trs = min(app, CEIL((len - cnt - sum), (num - 1)));
        cnt -= trs, sum += trs * num;
        if(cnt < req) return false;
        if(cnt + sum >= len) return true;
    }

    if(cnt < req) return false;
    if(cnt + sum >= len) return true;
    return false;

}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int l = 0, r = *max_element(a + 1, a + n + 1) + 1;
    while(l + 1 < r){
        int mid = (l + r) >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << l << "\n";
}

signed main(){
  ios::sync_with_stdio(0), cin.tie(0);
  int t; cin >> t;
  while(t --) solve();
  return 0;
}

::::