求助!第九个样例错了
查看原帖
求助!第九个样例错了
1046636
YFF1楼主2024/3/17 17:27

双指针做法求调!

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100005],t=0,cnt=0,cnt2=0,sum[100005],tot[100005],ans=0;
char c[100005];
int main () {
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++){
		if(c[i]=='1'){
			if(cnt2!=0){
				t++;
				a[t]=-cnt2;
				cnt2=0;
			}
			cnt++;
		}
		else {
			if(cnt!=0){
				t++;
				a[t]=cnt;
				cnt=0;
			}
			cnt2++;
		}
	}
	if(cnt2!=0){
		t++;
		a[t]=-1;
		cnt2=0;
	}
	if(cnt!=0){
		t++;
		a[t]=cnt;
		cnt=0;
	}
	for(int i=1;i<=t;i++){
		sum[i]=sum[i-1];
		if(a[i]<0)sum[i]++;
	}
	for(int i=1;i<=t;i++){
		tot[i]=tot[i-1];
		tot[i]+=abs(a[i]);	
	}
	int head=1,tail=1;
	while(head<=tail&&tail<=t){
		if(sum[tail]-sum[head-1]<=k){
			ans=max(ans,tot[tail]-tot[head-1]);
			tail++;
		}
		else head++; 
	}
	cout<<ans;
	return 0;
}
2024/3/17 17:27
加载中...