
这题说正解是前缀和+(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;
}