题解

沈思邈

2025-05-24 15:31:01

发布于：上海

26阅读

0回复

0点赞

朴实无华的单调队列，由于两端都需要删除，所以记得用 $deque$
我们只需要找 $sum_R-sum_L$ 作为结果即可，因此可以枚举 $R$ 找对于当前 $R$ 的最大 $ans$ ，又因为是找最大，则找对于 $sum_R$ 最小的 $sum_L$ ，故用单调递增队列

#include<iostream>
#include<deque>
using namespace std;
const int N=5e5+10;
deque<int>dq;
int n,m,a[N],psy[N],ans;//psy前缀和 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		psy[i]=psy[i-1]+a[i];
	}
	dq.push_back(0);
	for(int R=1;R<=n;R++){
		while(dq.size()&&psy[dq.back()]>psy[R])dq.pop_back();//维护单调递增
		while(dq.size()&&R-dq.front()>m)dq.pop_front();//维护差值不超过m
		ans=max(ans,psy[R]-psy[dq.front()]);
		dq.push_back(R);
	}
	cout<<ans;
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

「完全なる黄金の回転エネルギー」

#include <cstdio>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

const int MAXN = 5e5 + 10;
int n, m;
int p[MAXN];
long long sum[MAXN];
deque<int> dq;

int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        sum[i] = sum[i - 1] + p[i];
    }
    
    long long ans = -1e18;
    dq.push_back(0);
    
    for (int i = 1; i <= n; i++) {
    	
        while (!dq.empty() && dq.front() < i - m) 
            dq.pop_front();
        
        if (!dq.empty()) 
            ans = max(ans, sum[i] - sum[dq.front()]);
        else
            ans = max(ans, sum[i] - sum[i-1]);
            
        while (!dq.empty() && sum[dq.back()] >= sum[i]) 
            dq.pop_back();
        
        dq.push_back(i);
    }
    
    printf("%lld\n", ans);
    return 0;
}

为什么这种写法错了

1周前来自江苏