【单调队列】【3-21个人赛】【problmeB】

Problem B

Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 170 Accepted Submission(s) : 29

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

WKC有N个排成一排的灯泡，亮度分别为（A1,A2,……,An）。他希望从中找出一段连续的个数不小于A，且不超过B的灯泡，使得这些灯泡的亮度和S最大。
例如6个亮度为： 1， -3， 5， 1， -2， 3的灯泡，
当A=2，B=2或3时 S=5+1=6
当A=3，B=4时 S=5+1+(-2)+3=7

Input

第一行为一个整数T，表示有T组测试数组(T<=10)。
接下来为T组数组，每组的格式为：
第一行三个整数N,A,B(1<=A<=B<=N<=500000)。
第二行为N个整数，每个整数用空格隔开，表示这N个灯泡的亮度。|亮度|<=10000。

Output

对每组测试数据，输出一行，为所求的最大值S。

Sample Input

2
6 2 2
1 -3 5 1 -2 3
6 3 4
1 -3 5 1 -2 3

Sample Output

6
7

sum[i]存前缀和

枚举连续序列的初始点并找到【初始点+A-1，初始点+B-1】区间中的sum[i]的最大值更新ANS即可

复杂度N*（B-A）

但是我们可以看出在找最大值时这个区间是固定不动的，而且随着枚举初始点向左移，所以可以用单调队列来维护这个区间最大值

是单调队列的一个常用法

单调队列介绍在这里

http://blog.csdn.net/justmeh/article/details/5844650

1.不加二分

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
const int maxn=500000+5;
using namespace std;
struct node
{
    long long num;
    int pos;
};
long long N,A,B;
long long a[maxn],sum[maxn];
node queue[maxn];
int s=1,t=0;
void init()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
}
void input()
{
    s=1;t=0;
    scanf("%d%d%d",&N,&A,&B);
    for(int i=1;i<=N;i++)
    {
        scanf("%I64d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
}
void PUSH(long long aa,int bb)
{
    while(t!=s-1&&queue[t].num<=aa) t--;
    queue[++t].num=aa,queue[t].pos=bb;
}
void solve()
{
    long long ans;
    for(int i=A;i<=B;i++)
    PUSH(sum[i],i);
    ans=queue[s].num-sum[0];
    for(int i=2;i+A-1<=N;i++)
    {
        if(i+B-1<=N)
        PUSH(sum[i+B-1],i+B-1);
        while(queue[s].pos<i+A-1)
            s++;
        if(ans<queue[s].num-sum[i-1])ans=queue[s].num-sum[i-1];
    }
    printf("%I64d
",ans);
}
int main()
{
//	init();
	int T;
	cin>>T;
	while(T--)
    {
        input();
        solve();
    }
    return 0;
}

2.加二分

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
const int maxn=500000+5;
using namespace std;
struct node
{
    long long num;
    int pos;
};
long long N,A,B;
long long a[maxn],sum[maxn];
node queue[maxn];
int s=1,t=0;
void init()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
}
void input()
{
    s=1;t=0;
    scanf("%d%d%d",&N,&A,&B);
    for(int i=1;i<=N;i++)
    {
        scanf("%I64d",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
}
int FIND(int s,int t,int p)
{
    int m;
    while(s<t)
    {
        int m=(s+t)/2;
        if(queue[m].num<p) t=m;
        else s=m+1;
    }
    if(queue[s].num<=p) return s-1;
    else return s;
}
void PUSH(long long aa,int bb)
{
    int k=0;
    if(s>t)
    queue[++t].num=aa,queue[t].pos=bb;
    else {
            t=FIND(s,t,aa);
            queue[++t].num=aa,queue[t].pos=bb;
          }
}
void solve()
{
    long long ans;
    for(int i=A;i<=B;i++)
    PUSH(sum[i],i);
    ans=queue[s].num-sum[0];
    for(int i=2;i+A-1<=N;i++)
    {
        if(i+B-1<=N)
        PUSH(sum[i+B-1],i+B-1);
        while(queue[s].pos<i+A-1)
            s++;
        if(ans<queue[s].num-sum[i-1])ans=queue[s].num-sum[i-1];
    }
    printf("%I64d
",ans);
}
int main()
{
//	init();
	int T;
	cin>>T;
	while(T--)
    {
        input();
        solve();
    }
    return 0;
}