题意简述

给定数组，每次选奇偶性不同的一对数，将较小者替换为两者之和。求使所有数奇偶性相同的最少操作次数。

关键观察

• 奇 + 偶 = 奇。因此每次操作后，较小者必定变成奇数，较大者奇偶性不变。
• 如果最终全偶，则不能出现奇数，但操作会产生奇数，所以不可能由非全偶状态变成全偶。因此：
  • 初始全偶 $\to$ 答案 $0$；
  • 初始全奇 $\to$ 答案 $0$；
  • 否则目标只能是全奇，需要将所有偶数变成奇数。
• 每次操作若偶数小于奇数，偶数被替换为奇数，偶数数量减 $1$，奇数变大。
• 若偶数大于奇数，奇数被替换为更大的奇数，偶数不变。此时并不减少偶数数量，仅仅是“喂养”了奇数使其变大。
• 因此，需要维护当前最大的奇数 $M$（可取初始的最大奇数）。将偶数从小到大排序，依次处理：
  • 若 $M > e$，则一次操作消灭 $e$，$M \gets M + e$，操作数 $+1$；
  • 若 $M < e$，则需要先“喂养”：第一次操作将 $M$ 变成 $M+e$（奇数变大，偶数仍保留），第二次操作再用新 $M$ 消灭 $e$，操作数 $+2$，$M \gets M + 2e$。

贪心地从小到大处理偶数，可以使 $M$ 稳步增长，避免不必要的“喂养”次数。该策略是最优的。

时间复杂度 $O(n \log n)$ 每组，总复杂度 $O(\sum n \log n) \le 2\cdot10^5 \log n$，足够。

参考代码

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    int max_odd = -1;
    vector<int> evens;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] % 2 == 1) {
            max_odd = max(max_odd, a[i]);
        } else {
            evens.push_back(a[i]);
        }
    }

    if (evens.empty() || max_odd == -1) {
        // 全奇或全偶
        cout << "0\n";
        return;
    }

    sort(evens.begin(), evens.end());
    ll M = max_odd;
    ll ans = 0;
    for (int e : evens) {
        if (M > e) {
            ans += 1;
            M += e;
        } else {
            ans += 2;
            M += 2LL * e;
        }
    }
    cout << ans << "\n";
}

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