题目描述
给定一个长度为n的序列,你有一次机会选中一段连续的长度不超过d的区间,将里面所有数字全部修改为0。请找到最长的一段连续区间,使得该区间内所有数字之和不超过p。
输入格式:
第一行包含三个整数n,p,d(1<=d<=n<=2000000,0<=p<=10^16)。第二行包含n个正整数,依次表示序列中每个数w。
输出格式:
包含一行一个正整数,即修改后能找到的最长的符合条件的区间的长度。
题解:
发现,肯定要选择最多的d变成0,不然不优。并且,如果以i作为结尾,左端点为j的话,那么如果以i+1作为结尾,左端点不可能比j小。
所以,可以用一个双指针,维护L,R,
L、R为一个合法区间条件是,L~R的数的和,减去最大的长度为d的和,总和少于等于p
对于给定R,L不满足的时候,就把L右移即可。
至于L~R中长度等于d的最大的和,可以用一个单调队列维护。
复杂度O(n)
代码:
#includeusing namespace std;typedef long long ll;const int N=2000000+10;int n,d;ll p;int ans;int q[N],l,r;ll sum[N],a[N];int main(){ scanf("%d%lld%d",&n,&p,&d); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } int L=1,R=1; l=1,r=0; q[++r]=d; for(R=d;R<=n;R++){ //cout< < p){ L++; while(l<=r&&q[l]-d+1 sum[q[r]]-sum[q[r]-d]) r--; q[++r]=R+1; } } printf("%d",ans); return 0;}