[洛谷]P3594 [POI2015]WIL-Wilcze doły (#单调队列)

题目描述

给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。

输入格式

第一行包含三个整数n,p,d(1<=d<=n<=2000000，0<=p<=10^16)。第二行包含n个正整数，依次表示序列中每个数wi。

输出格式

包含一行一个正整数，即修改后能找到的最长的符合条件的区间的长度。

输入输出样例

输入 #1复制

9 7 2
3 4 1 9 4 1 7 1 3

输出 #1复制

5

说明/提示

给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。

请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。

思路

选择每一个位置i作为结尾能形成的最长区间的左端点是单调不降的。

#include <stdio.h>
#include <iostream>
#include <deque>
#define N 2000001
#define ll long long int 
using namespace std;
ll n,p,d,s,t[N],last(1);
struct node
{
	ll val;
	ll position;
	ll sum;
}a[N];
deque<node> dq;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	register ll i,j;
	cin>>n>>p>>d;
	for(i=1;i<=n;i++)
	{
		cin>>a[i].val;//a[i]
		a[i].position=i;//序列位置 
		a[i].sum=a[i-1].sum+a[i].val;//前缀和 
	}
	for(i=d;i<=n;i++)
	{
		t[i]=a[i].sum-a[i-d].sum;//算区间[i-d+1,i]的和 
	}
	s=d;//答案至少为d 
	a[0].position=d;
	dq.push_back(a[0]);
	for(i=d+1;i<=n;i++)
	{
		while(!dq.empty() && t[dq.back().position]<t[i])
			dq.pop_back();
		dq.push_back(a[i]);
		while(!dq.empty() && dq.front().position-d+1<last)//如果队首元素的左端点比last小，那就弹出 
			dq.pop_front();
		while(!dq.empty() && a[i].sum-a[last-1].sum-t[dq.front().position]>p)
		{
			last++;
			while(!dq.empty() && dq.front().position-d+1<last)
				dq.pop_front();
		}
		s=max(s,i-last+1);
	}
	cout<<s<<endl;
	return 0;
}

最后

以上就是优美戒指为你收集整理的[洛谷]P3594 [POI2015]WIL-Wilcze doły (#单调队列)的全部内容，希望文章能够帮你解决[洛谷]P3594 [POI2015]WIL-Wilcze doły (#单调队列)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。