JZOJ 1844——数数

本文主要是介绍JZOJ 1844——数数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

仍然是预处理sum[i]表示前i个数的和，只枚举右端点r
问题就转换成了在sum[r-k..r-1]中找一个最小值。
那么我们维护一个元素单调递增的队列
每次处理完一个r后把队尾所有不小于sum[r]的元素删掉后把sum[r]放进队尾。那么每次只用把队头中元素在原数组中的下标

---

代码如下：

#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iostream>
#define MAXN 110000
#define INF 100000009
using namespace std;
long long sum[MAXN];
int q[MAXN];
int n,k,head,tail;
long long ans;
int main()
{scanf("%d%d",&n,&k);ans=-INF;q[0]=0;sum[0]=0;for (int i=1;i<=n;i++){int x;scanf("%d",&x);sum[i]=sum[i-1]+x;while (q[head]<i-k) head++;while (sum[i]<=sum[q[tail]]&&tail>=head)tail--;q[++tail]=i;ans=max(ans,sum[i]-sum[q[head]]);}printf("%lld",ans);return 0;
}

这篇关于JZOJ 1844——数数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---