清新区住房和城乡建设局网站网推app

题目内容

原题链接

给定一个长度为 $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 <bits/stdc++.h>
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;
}