01子段wa0

常规
1 
#include <bits/stdc++.h>
using namespace std;
int sum0[1005];
int sum1[1005];
char s[1005];
int n;
bool check(int m,int n)
{
	for(int x=n,y=n;x>=1;x--)
	{
		while(sum0[x]-sum0[y-1]<=m and y>0)y--;
		if(sum1[y]-sum1[0]+sum1[n]-sum1[x]<=m) return true;
	}
	return false;
}
int main()
{
	cin>>n;
	while (n--)
	{
		scanf("%s",s+1);
		int len=strlen(s+1);
		for(int i=1;i<=len;i++)
		{
			sum1[i]=sum1[i-1];
			sum0[i]=sum0[i-1];
			if(s[i]=='1') sum1[i]+=1;
			else sum0[i]+=1;
		}
		int L=-1,R=len+1;
		while (L+1<R)
		{
			int mid=(L+R)>>1;
			if(check(mid,len)==true)R=mid;
			else L=mid;
		}
		cout<<L;
	}
}
2 个赞
2

发体面

1 个赞
3

A. 零一子段

Problem ID: 9739

Contest ID: 6577

必做题

题目描述

给定一个长度为 n 的 01 字符串。你需要从前面删去若干个字符（可以为 0 个），再从后面删去若干个字符（可以为 0 个），使得以下两者较大的一个尽可能小：

  • 删去的 1 的个数。
  • 留下的 0 的个数。注意你可以删空整个串。

输入格式

第一行一个整数 T，表示数据组数，

每组数据一行一个 01 字符串。

输出格式

每组数据输出一行，代表代价的最小值。

样例输入

5
101110110
1001001001001
0000111111
00000
1111

样例输出

1
3
0
0
0

数据规模

1≤T≤1041≤T≤104，1≤∣s∣≤2×1051≤∣s∣≤2×105，∑∣s∣≤2×105∑∣s∣≤2×105。

加载最近代码

1

​

Debug提示

1 个赞
4

1.最后输出的是r
2.while开头没有初始化
3.数组sum0,sum1,s都不够大

1 个赞
5

#include<bits/stdc++.h>
using namespace std;
const int INT=1e5+1;
long long sum0[INT],sum1[INT];
char s[200005];
int n;
bool check(int m,int n) {
for(int x=n,y=n; x>=1; x–) {
while(sum0-sum0[y-1]<=m and y>0) y–;
if(sum1[y]-sum1[0]+sum1[n]-sum1<=m) return true;
}
return false;
}
int main() {
cin>>n;
while(n–) {
memset(sum1,0,sizeof(sum1));
memset(sum0,0,sizeof(sum0));
scanf(“%s”,s+1);
int len=strlen(s+1);
for(int i=1; i<=len; i++){
sum1[i]=sum1[i-1];
sum0[i]=sum0[i-1];
if(s[i]==‘1’) sum1[i]+=1;
else sum0[i]+=1;
}

	int l=-1,r=len+1;
	while(l+1<r){
		int mid=(l+r)/2;
		if(check(mid,len)==true) r=mid;
		else l=mid;
	}
	cout<<r<<endl;
}

}

1 个赞