深圳国税局网站怎么做票种核定/大庆建站公司
喵哈哈村的魔力源泉（4）
发布时间: 2017年5月9日 20:59 最后更新: 2017年5月9日 20:59 时间限制: 1000ms 内存限制: 128M
喵哈哈村有一个魔法源泉，里面有无穷无尽的力量。
但是前提是你能答出这样一个问题：
给你n个数a[1]，a[2]，a[3]，......，a[n]，然后再给你一个k。
定义sum[l,r]=a[l]+a[l+1]+a[l+2].....+a[r-1]+a[r]，但是必须满足r-l+1<=k
让你输出最大的sum[l,r]
第一行有2个数，n,k
第二行有n个数，a1,a2,...,an
对于100%的数据，n≤1000000,k≤n,−1000≤ai≤1000(1≤i≤n)
输出只有一行，sum[i,j] 的最大值
复制
7 53 6 -8 9 -12 1 2
10
思路很清晰，就是求
f(i) = sum[i]-min{sum[k]|i-M≤k≤i}
然而n很大，故不能用n^2的方法来求解，需要优先队列优化一发
讲解博客：http://blog.csdn.net/oiljt12138/article/details/51174560
#include<vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
#define maxn 1000005
#define Mod 1000000007
struct node
{ll c,id;
}q[maxn];
int head,rear;
ll sum[maxn],ans;
int main(void)
{int i,j,x,n,m;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d",&x);sum[i]=sum[i-1]+x;}for(i=1;i<=n;i++){ll tmp=sum[i];tmp-=q[head].c;ans=max(ans,tmp);while(head<=rear && q[rear].c>sum[i])rear--;q[++rear].c=sum[i];q[rear].id=i;while(q[head].id<=i-m)head++;}printf("%lld\n",ans);return 0;
}