?大致题意 : 给定一个01串, 可对进行一些操作: 从字符串前后删除一些字串(可以为0), 操作的花费为, 删除的字符1的数量与剩余的字符0数量的最大值
思路 : 本题有多种做法(最多的为二分和双指针), 这里用一种贪心的做法, 做以下定义:
- S1表示字符串中 '1' 的数量;
- lent表示字串t的长度
- t1表示任一字串中'1'的数量;
- t0表示任一字串中'0'的数量.
对于操作后的字串t, 答案即为max(t0, S1-t1) = max(t0+t1, S1) - t1 = max(lent, S1) - t1;
对lent进行分析:
- 当lent<=S1时, res = S1 - t1, 要使答案尽可能小, 则要让t1尽可能大, 当lent = S1 时t1最大, res最小, res = S1 - t1
- 当lent>=S1时, res = lent - t1 = t0,?要使答案尽可能小, 则要让t0尽可能小, 则lent尽可能小, 当lent = S1 时取得最小值, res = S1 - t1
即字串长度为S1时, res能取得最小值, res = S1 - t1, 即求字串长度为S1时, 字串中 '1' 数量最大时的res, 可以用前缀和处理区间中' 1' 的数量, 枚举以下字串即可, 时间复杂度O(n)
代码如下:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <iomanip>
using namespace std;
stringstream ss;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5+10, mod = 1e9+7;
const int INF = 0x3f3f3f3f;
string str;
int s[N];
void solve()
{
cin>>str;
int n = str.size(), cnt = count(str.begin(), str.end(), '1');
str = " "+str;
for(int i = 1; i<=n; i++)
s[i] = s[i-1] + (str[i] == '0');
int res = cnt;
for(int i = cnt; i<=n; i++)
{
res = min(res, s[i] - s[i-cnt]);
}
cout<<res<<"\n";
}
int main()
{
int T;
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>T;
while(T -- )
{
solve();
}
}
