单调队列.

Table of Contents

  1. Description
  2. Solution

Description

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

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

Solution

首先, 我们要改就一定改掉完全一段长为$d$的区间.

然后我们对这个区间和跑单调队列, 这时我们得到了这个位置以及之前的区间和最大值. 不难发现随着$i$右移, 可行的左端点一定会随之右移, 这个过程可以跟随单调队列跑, 注意每次删去不合法的队头(也就是队头删去$d$个位置后小于左端点). 我们不断右移左端点, 直到区间和小于等于$p$, 同时队头也跟随着移动. 最后更新答案.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

const int maxn = 2e+6 + 5;

typedef long long ll;

int n, d;
ll a[maxn], p, hd, tl, sum[maxn], inv[maxn];
int que[maxn];

inline int rd()
{
	register int x = 0; char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
	return x;
}
inline ll rdll()
{
	register ll x = 0; char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
	return x;
}

int main()
{
	n = rd(); p = rdll(); d = rd();
	for(int i = 1; i <= n; ++i) a[i] = rdll(), sum[i] = sum[i - 1] + a[i];
	for(int i = d; i <= n; ++i) inv[i] = sum[i] - sum[i - d];
	int len = d, lft = 1; hd = 0; tl = 1;
	que[0] = d;
	for(int i = d + 1; i <= n; ++i)
	{
		while(hd < tl && inv[i] > inv[que[tl - 1]]) --tl;
		que[tl++] = i;
		while(hd < tl && que[hd] - d + 1 < lft) hd++;
		while(hd < tl && sum[i] - sum[lft - 1] - inv[que[hd]] > p)
		{
			++lft; //puts("+");
			while(hd < tl && que[hd] - d + 1 < lft) hd++;
		}
		
		len = max(len, i - lft + 1);
		//printf("%d %d\n", i, len);
	}
	printf("%d\n", len);
	return 0;
}