给一个长度为 nn 的 0101 字符串,你可以任意选择下面两个操作任意次: 从左往右删除任意长度连续段 从右往左删除任意长度连续段 现在要求 max(删掉的1,剩下的0)max(删掉的1,剩下的0) 最小。
时间: 2024-02-16 22:59:47 浏览: 14
可以使用二分答案 + 贪心的思想来解决这个问题。
首先,我们二分答案 $mid$,表示最后剩下的 $0$ 的个数为 $mid$。然后,我们可以贪心地考虑,对于每个 $mid$,如果从左往右删除的 $1$ 的个数 $cnt_1$ 小于等于从右往左删除的 $1$ 的个数 $cnt_2$,那么就从左往右删除 $cnt_1$ 个 $1$,否则就从右往左删除 $cnt_2$ 个 $1$。最后如果剩下的 $0$ 的个数小于 $mid$,说明二分答案偏大,否则说明偏小。
具体实现可以用双指针来做,从左往右维护一个区间,使得区间内 $1$ 的个数不超过 $mid$,然后从右往左扫描字符串,维护一个指针,使得指针右边的 $1$ 的个数不超过 $mid$,然后在这个过程中更新答案即可。
下面是代码实现(使用 C++11):
```cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int n;
string s;
bool check(int mid) {
int cnt1 = 0, cnt2 = 0; // 左右两侧删除的 1 的个数
int l = 0, r = n - 1; // 双指针
while (l <= r) {
while (l <= r && s[l] == '0') ++l; // 左指针右移
while (l <= r && s[r] == '0') --r; // 右指针左移
int len = 0;
while (l + len <= r && s[l + len] == '1' && cnt1 + len + 1 <= mid) ++len; // 左侧删除
cnt1 += len;
len = 0;
while (l <= r - len && s[r - len] == '1' && cnt2 + len + 1 <= mid) ++len; // 右侧删除
cnt2 += len;
if (cnt1 > mid || cnt2 > mid) return false; // 如果删除的 1 的个数超过了 mid,说明不合法
if (l > r) break; // 如果 l > r,说明已经扫描完了
if (cnt1 + cnt2 + r - l + 1 <= mid) return true; // 如果剩下的 0 的个数不超过 mid,说明合法
}
return false;
}
int main() {
cin >> n >> s;
int l = 0, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
int cnt1 = 0, cnt2 = 0; // 左右两侧删除的 1 的个数
int l = 0, r = n - 1; // 双指针
while (l <= r) {
while (l <= r && s[l] == '0') ++l; // 左指针右移
while (l <= r && s[r] == '0') --r; // 右指针左移
int len = 0;
while (l + len <= r && s[l + len] == '1' && cnt1 + len + 1 <= ans) ++len; // 左侧删除
cnt1 += len;
len = 0;
while (l <= r - len && s[r - len] == '1' && cnt2 + len + 1 <= ans) ++len; // 右侧删除
cnt2 += len;
if (cnt1 > ans || cnt2 > ans) break; // 如果删除的 1 的个数超过了 ans,说明不合法
if (l > r) break; // 如果 l > r,说明已经扫描完了
if (cnt1 + cnt2 + r - l + 1 <= ans) break; // 如果剩下的 0 的个数不超过 ans,说明合法
}
cout << max(cnt1 + cnt2, n - ans) << endl;
return 0;
}
```
时间复杂度为 $O(n \log n)$。