求此代码时间复杂度
  • 板块学术版
  • 楼主Aesyl
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/10/19 17:34
  • 上次更新2023/11/2 12:47:50
查看原帖
求此代码时间复杂度
1062944
Aesyl楼主2023/10/19 17:34

P3594,正解是单调队列,想用双指针+堆卡过去没成功。

#include<bits/stdc++.h>
#define int long long
#define N 2000005
using namespace std;
int n,m,d,a[N],s[N],ans;
priority_queue<int>q;
map<int,int>mp;
signed main(){
	ios::sync_with_stdio(false);
	read(n),read(m),read(d);
	for(int i=1;i<=n;i++) read(a[i]),s[i]=s[i-1]+a[i];
	for(int l=1,r=d;r<=n;r++){
		q.push(s[r]-s[r-d]),mp[s[r]-s[r-d]]++;
		while(true){
			while(!mp[q.top()]) q.pop();
			if(s[r]-s[l-1]-q.top()>m) l++,mp[s[l+d-1]-s[l-1]]--;
			else break;
		}
		ans=max(ans,r-l+1);
	}
	write(ans);
    return 0;
}

2023/10/19 17:34
加载中...