cf2179 E. Blackslex and Girls 题解

题意

有 n 个选区，字符串 s 表示每个选区获胜方（0 表示 A 赢，1 表示 B 赢），每个选区至少要有 p[i] 张总票。A 党有 x 票，B 党有 y 票，问是否存在分配方案。

思路

对于每个选区，要获胜且票数 ≥ p[i]，获胜方至少需要 ⌊p[i]/2⌋ + 1 票，失败方至少 ⌊p[i]/2⌋ 票。
记：

• sumA = 所有 0 选区的获胜方最小票数和；
• sumB = 所有 1 选区的获胜方最小票数和；
• sumP = 所有 p[i] 之和。

先检查总票数：x + y ≥ sumP，否则无解。

分类讨论

1. 既有 0 也有 1：只需 x ≥ sumA 且 y ≥ sumB。
2. 全为 0：还需满足每个选区 A > B，即 x ≥ sumA 且 x ≥ y + n。
3. 全为 1：对称地，y ≥ sumB 且 y ≥ x + n。

代码

#include <bits/stdc++.h>
#include <cstddef>
using ll = long long;
using namespace std;
const int N = 2e5 + 10, mod = 998244353, inf = LLONG_MAX;
ll n, x, y, a[N];
string s;
void solve() {cin >> n >> x >> y >> s;ll sum = 0;ll sumx = 0, sumy = 0;for (int i = 0; i < n; i++) {cin >> a[i];sum += a[i];if (s[i] == '0') {sumx += a[i] / 2 + 1;} else {sumy += a[i] / 2 + 1;}}if (x + y < sum) {cout << "NO" << '\n';return;}if (sumx == 0) {//全1if (y >= sumy && y >= n + x) {cout << "YES" << '\n';} else {cout << "NO" << '\n';}return;}if (sumy == 0) {//全0if (x >= sumx && x >= n + y) {cout << "YES" << '\n';} else {cout << "NO" << '\n';}return;}if (x >= sumx & y >= sumy) {cout << "YES" << '\n';} else {cout << "NO" << '\n';}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}