【每日一题】CF1680C. Binary String | 双指针 | 简单

题目内容

原题链接

给定一个长度为 $n$ 的 $01$ 字符串，对于一个子串 $sub$ ，子串内部的 $0$ 的数量为 $x$ ，子串以外的 $1$ 的数量为 $y$ ，子串的代价为 $max(x,y)$ ，问代价最小是多少。

数据范围

• $1\le n\le 2\times 10^5$

题解

解法1

二分答案 $mid$，枚举子串右端点，当 $x\ge y$ ，则不停移动左端点。然后取 $max$ 判断是否存在一个子串的代价小于等于 $mid$ 。

时间复杂度：$O(n\log n)$

解法2

从二分答案中可以考虑到，枚举右端点，当 $x\ge y$ ，就需要不停移动左端点，直到 $x\le y$ 。
这样就不需要二分答案了，只是一个双指针。

时间复杂度：$O(n)$

代码

#include 
using namespace std;

void solve() {
    string s;
    cin >> s;

    int n = int(s.size());

    int all1 = 0;
    for (auto c: s) all1 += c == '1';

    int ans = n - all1;
    int in0 = 0, out1 = all1;
    for (int r = 0, l = 0; r < n; ++r) {
        int v = s[r] - '0';
        if (v == 0) in0 += 1;
        else out1 -= 1;
        while (l <= r && in0 > out1) {
            v = s[l] - '0';
            if (v == 0) in0 -= 1;
            else out1 += 1;
            l += 1;
        }
        ans = min(ans, max(in0, out1));
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40