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
例如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。
接下来为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\n",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\n",ans);
}
int main()
{
// init();
int T;
cin>>T;
while(T--)
{
input();
solve();
}
return 0;
}