已ac代码求问
  • 板块灌水区
  • 楼主lucy2012
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/8/22 20:49
  • 上次更新2024/8/22 23:41:30
查看原帖
已ac代码求问
1252442
lucy2012楼主2024/8/22 20:49

这题说正解是前缀和+(st表,线段树,单调队列)维护区间最小值,我一个只学了csp-j的蒟蒻一点也不会awa。

但是我ac了,思路是通过环,如果该数为负就不算在最后的答案总和里,往前加,如果还是负数就继续标记,不算在答案里,最后看没有被标记的数有多少。

所以问问大佬们我的思路和代码是不是卡过去的或者不是正解,顺便球球正解详细的思路QwQ。

code:

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[300010],ans[300010],cnt;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		if(a[i]>=0){
			continue;
		} 
		long long now=(i+n-2)%n+1,sum=a[i];
		ans[i]=1;
		while(now!=i){
			sum+=a[now];
			if(sum>=0){
				break;
			}
			ans[now]=1;
			now=(now+n-2)%n+1;
		}
	}
	for(int i=1;i<=n;i++){
		if(ans[i]!=1){
			cnt++;
		}
	}
	cout<<cnt;
	return 0;
} 
2024/8/22 20:49
加载中...