49分求助
查看原帖
49分求助
222057
joy2010WonderMaker楼主2022/2/15 17:06
#include<bits/stdc++.h>
using namespace std;
int read(){
    char c=getchar();
	int x=0;
	bool f=0;
    for(;!isdigit(c);c=getchar())
		f^=!(c^45);
    for(;isdigit(c);c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
    if(f)
		x=-x;
	return x;
}
void write(int x){
	if(x<0)
		putchar('-');
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
int n,a[100005],maxn,f,cnt,s[100005],tot,sum[100005],ans,pos,tmp,k,l;
bool fl,vis[100005],p[100005];
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]<0&&!f)
			f=i;
		if(a[i]>0&&f)
			maxn=max(maxn,i-f),f=0;
	}
	if(f)
		maxn=max(maxn,n-f);
	for(int i=1;i<=n;i++){
		if(a[i]<0)
			cnt++;
		else
			s[max(i-2*cnt-1,1)-cnt+1]=min(2*cnt,i-2),cnt=0;
	}
	if(cnt)
		s[max(n-2*cnt,1)-cnt+1]=min(2*cnt,n-1),cnt=0;
	for(int i=1;i<=n;i++){
		if(s[i])
			tot=max(tot,i+s[i]-1);
		if(i<=tot)
			vis[i]=true;
	}
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1];
		if(vis[i])
			sum[i]++;
	}
	for(int i=1;i<=n;i++)
		if(a[i]<0)
			cnt++;
		else{
			if(cnt==maxn)
				p[i-cnt]=true;
			cnt=0;
		}
	if(cnt==maxn)
		p[n]=true;
	for(int i=1;i<=n;i++)
		if(p[i]){
			pos=max(i-maxn*3,0);
			tmp=sum[i]-sum[pos];
			ans=max(ans,maxn*3-tmp);
		}
	for(int i=1;i<=n;i++)
		if(p[i]){
			pos=max(i-maxn*3,0);
			tmp=sum[i]-sum[pos];
			if(maxn*3-tmp==ans)
				k=max(i-3*maxn,1),l=min(3*maxn,i-1);
		}
	for(int i=k;i<=k+l-1;i++)
		vis[i]=true;
	ans=0;
	for(int i=1;i<=n;i++)
		if(vis[i])
			ans++;
	write(ans);
	return 0;
}

2022/2/15 17:06
加载中...