单调队列15分 求助
查看原帖
单调队列15分 求助
790282
Ribaudiaux楼主2022/11/29 22:58

我不理解TAT感觉思路没有问题啊…

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+2, M=1e6+2;
int sum[N], arr[M];
deque<int> q, num;
int ans;
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &arr[i]);
        sum[i]=sum[i-1]+arr[i];
    }
    for(int i=n+1;i<=2*n;i++){
        sum[i]=sum[i-1]+arr[i-n];
    }
    for(int i=1;i<=2*n-1;i++){
        if(!q.empty()&&q.back()>sum[i]){
            q.pop_back();
            num.pop_back();
        }
        q.push_back(sum[i]);
        num.push_back(i);
        if(i-num.front()>=n){
            q.pop_front(); num.pop_front();
        }
        if(i>=n){
            if(q.front()-sum[i-n]>=0) ans++;
        }
    }
    printf("%d", ans);
    return 0;
}
2022/11/29 22:58
加载中...