题解：CF2189E Majority Wins?

block_in_mc · 2026-01-24 00:10:15 · 题解

不难发现一次操作花费了 r-l+1 的代价删除了 r-l 个字符，这其实等价于每删除一个字符要花费 1 的代价，同时每次操作要额外花费 1 的代价。由于最后删除的字符总是 n-1 个，所以总代价为 n-1 加上操作次数，因此最小化代价即为最小化操作次数。

首先可以发现，若字符串中存在一个 \texttt1，则总是可以在 4 次操作内将整个串变为 \texttt1。具体地，选择其中任意一个 \texttt1，对左侧的所有数（如果有）进行一次操作，再将左侧变成的数与选定的 \texttt1 进行操作就总能将左侧完全删除，右侧也是同理，即 \cdots\texttt{1}\cdots\rightarrow\texttt{?1}\cdots\rightarrow\texttt{1}\cdots\rightarrow\texttt{1?}\rightarrow\texttt{1}。

由于总能在 4 次操作内完成，考虑对所需要的操作次数进行分类讨论：

• 答案为 -1。这要求字符串中不存在 \texttt1。
• 能在 1 次操作内变为 \texttt{1}。这要求字符串 1 的数量大于等于 0 的数量。
• 能在 2 次操作内变为 \texttt{1}。那么第一次操作的目标是让 \texttt0 的数量减 \texttt1 的数量小于等于 0。若第一次操作变成的字符为 \texttt1，那么操作 \texttt{01} 或 \texttt{10} 一定是最优的；否则应该让第一次操作选择的子串中 \texttt0 的数量减 \texttt1 的数量尽量大，这使用前缀和容易算出。
• 能在 3 次操作内变为 \texttt{1}。按照与之前类似的操作方法，充要条件为：要么存在子串 \texttt{11}，对应操作为 \cdots\texttt{11}\cdots\rightarrow\texttt{?11?}\rightarrow\texttt{1}，要么存在一个前缀或者一个后缀满足经过一次操作可以变为 \texttt1，对应操作为 (\cdots)\cdots\rightarrow\texttt{1}\cdots\rightarrow\texttt{1?}\rightarrow\texttt{1}。必要性可以通过手模几个样例进行验证。
• 否则总能在 4 次操作内变为 \texttt{1}。

因此我们解决了这道题，时间复杂度 O(n)。代码并不难写：

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n; string s;
    cin >> n >> s; s = " " + s;
    if (n == 1 && s == " 1") return cout << 0 << '\n', void();
    int cnt0 = count(s.begin(), s.end(), '0'), cnt1 = n - cnt0;
    if (cnt0 == n) return cout << -1 << '\n', void();
    if (cnt1 >= cnt0) return cout << n << '\n', void();
    if (cnt1 >= cnt0 - 1) return cout << n + 1 << '\n', void();
    vector<int> sum(n + 10); int mn = 0, res = 0, suf = 0;
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + (s[i] == '0' ? 1 : -1);
        res = max(res, sum[i] - mn - 1), mn = min(mn, sum[i]);
    }
    if ((cnt0 - cnt1) - res <= 0) return cout << n + 1 << '\n', void();
    if (count_if(sum.begin() + 1, sum.begin() + n + 1, [&](int v) { return v <= 0; }) >= 1) return cout << n + 2 << '\n', void();
    for (int i = n; i >= 1; i--) {
        suf += (s[i] == '0' ? 1 : -1);
        if (s[i] == '1' && s[i - 1] == '1') return cout << n + 2 << '\n', void();
        if (suf <= 0) return cout << n + 2 << '\n', void();
    }
    cout << n + 3 << '\n';
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}