Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom8月前

12/10
10:02
单调栈/队列

[bzoj 4385] [POI2015]Wilcze doły

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

5

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

将第4个和第5个数修改为0,然后可以选出区间[2,6],总和为4+1+0+0+1=6。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

设s为原数组的前缀和,i是左端点,j是右端点,那么只要满足

s[j]-s[i]-max(s[x]-s[x-d])<=p (i<=x-d<x<=j) 这个区间(i,j]就是满足条件的

很明显随着j的增加,i和x都只会向右移动,那么只要把每个s[x]-s[x-d]放入一个单调队列中进行维护就行了

 

[bzoj 4385] [POI2015]Wilcze doły