Wilcze doły

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

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

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

之前不知道单调队列这个东西，所以这个题就没有思路、本来想着是暴力尺取、感觉不会过所以就、、、

两个学习单调队列的链接

https://blog.csdn.net/A_Bright_CH/article/details/77076228

https://blog.csdn.net/u011893609/article/details/78806089

然后，这题就是个模板、大概，总之知道单调队列就和容易想了

然后是Ac代码

#include
using namespace std;
typedef long long ll;
typedef pair pll;
const int maxn = 2e6+7;
int n,d;
ll p,F[maxn];
deque Q;
int main(){scanf("%d%lld%d",&n,&p,&d);for(int i=1;i<=n;i++)scanf("%lld",&F[i]),F[i] += F[i-1];int ans = d,l = 0;for(int r=d,j=1;r<=n;j++,r++){while(!Q.empty() && Q.back().first <= F[j+d-1]-F[j-1])Q.pop_back();Q.push_back(make_pair(F[j+d-1]-F[j-1],j));while(l p){l++;if(l>=Q.front().second)Q.pop_front();}ans = max(ans,r-l);}printf("%d\n",ans);return 0;
}

既然代码A了，自然要优化一波，先加个读入挂，然后，pair没必要啊，只用开一个int表示位置就可以了

所以，优化后的代码

#include
using namespace std;
typedef long long ll;
const int maxn = 2e6+7;
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c))c = getchar();if(c == '-')Nig = -1,c = getchar();while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();return Nig*x;
}
#define read read()
int n,d;
ll p,F[maxn];
ll Gets(int i){return F[i+d-1]-F[i-1];}
deque Q;
int main(){n = read,p = read,d = read;for(int i=1;i<=n;i++)F[i] = read,F[i] += F[i-1];int ans = d,l = 0;for(int r=d,j=1;r<=n;j++,r++){while(!Q.empty() && Gets(Q.back()) <= Gets(j))Q.pop_back();Q.push_back(j);while(l p){l++;if(l>=Q.front())Q.pop_front();}ans = max(ans,r-l);}printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！