C. Asuna and the Mosquitoes 详细题解

一、问题重述

给定一个长度为 $n$ 的非负整数数组 $a$（初始全部为正）。允许操作：选择 $i \ne j$ 使得 $a_i + a_j$ 为奇数且 $a_i > 0$，然后 $a_i \leftarrow a_i - 1$，$a_j \leftarrow a_j + 1$。求经过任意次操作后，数组最大值最大能是多少。

---

二、核心观察

2.1 操作对奇偶性的影响

• $a_i + a_j$ 为奇数 $\iff$ 一个奇数、一个偶数。
• 操作：奇数 $-1$ 变偶数，偶数 $+1$ 变奇数。即奇偶性互换。
• 因此，操作不改变数组中奇数的个数 $k$。

2.2 总和的守恒

每次操作总和不变：$(-1 + 1) = 0$。因此总和 $S = \sum a_i$ 是常数。

---

三、两种情况讨论

情况 1：所有数奇偶性相同（全奇或全偶）

无法进行任何操作（因为找不到一对奇偶不同的数）。答案为 $\max(a)$。

情况 2：既有奇数又有偶数

设 $k$ 为奇数个数，$S$ 为总和。

上界：最终最大值 $\le S - k + 1$。
原因：奇数个数 $k$ 不变，最终数组至少要有 $k$ 个奇数。总和固定，让一个数尽可能大时，其余数至少为 $1$（因为奇数最小为 $1$）。若最大值为 $M$，则：

$$M + (k-1)\cdot 1 + 0 + \cdots \le S \Rightarrow M \le S - k + 1 $$

可达性：通过构造可以达到 $S - k + 1$：

1. 将所有偶数加到某一个奇数 $A$ 上（通过操作把偶数逐个合并到 $A$）。
2. 此时数组变为：$A + \text{所有偶数和}$（一个奇数），其余 $k-1$ 个奇数保持不变，剩余位置为 $0$。
3. 对于剩下的 $k-1$ 个奇数，每次：
   • 将该奇数转移 $1$ 到一个 $0$ 位置（产生一个偶数 $1$，原奇数变为偶数）
   • 再将这个偶数合并到 $A$ 上
   • 重复直到只剩一个奇数 $A$ 和 $k-1$ 个 $1$
4. 最终数组为：$[S - k + 1, 1, 1, \dots, 1, 0, 0, \dots]$，最大值 $S - k + 1$。

---

四、标程代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    long long sum = 0;
    int odd_cnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
        odd_cnt += (a[i] & 1);
    }
    
    if (odd_cnt == 0 || odd_cnt == n) {
        // 全奇或全偶，无法操作
        cout << *max_element(a.begin(), a.end()) << '\n';
    } else {
        // 既有奇数又有偶数
        cout << sum - odd_cnt + 1 << '\n';
    }
}

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

---

五、示例验证

示例 1：$[5,3,9]$

• 全奇数 → $odd\_cnt = 3$，输出 $\max = 9$ ✅

示例 2：$[3,2]$

• $odd\_cnt = 1$，$sum = 5$，输出 $5 - 1 + 1 = 5$ ✅

示例 3：$[1,2,2,1]$

• $odd\_cnt = 2$，$sum = 6$，输出 $6 - 2 + 1 = 5$ ✅

示例 4：$[5,4,3,2,9]$

• $odd\_cnt = 3$，$sum = 23$，输出 $23 - 3 + 1 = 21$ ✅

---

六、复杂度分析

• 每个测试用例 $O(n)$
• 总 $n \le 2 \times 10^5$，完全可行

---

七、总结

情况	条件	答案
全奇或全偶	$odd\_cnt = 0$ 或 $odd\_cnt = n$	$\max(a)$
奇偶混合	其他	$S - odd\_cnt + 1$

核心：操作不改变奇数个数 $k$，总和 $S$ 固定，最大元素最多为 $S - k + 1$，且该上界可达。