Cogs 2382. [HZOI 2016]最佳序列

★☆ 输入文件：bestseq.in 输出文件：bestseq.out 简单对比
时间限制：1 s 内存限制：128 MB

【题目描述】

你得到了一个N个非负整数组成的序列A。

我们称由序列A的连续若干项组成的新序列为A的一个连续子序列。给出两个正整数LR(L<=R)。称A的每一个长度不小于L且不大于R的连续子序列为一个纯洁序列，定义纯洁度为纯洁序列的所有元素的平均值。

请你求出所有纯洁序列中的纯洁度的最大值。

【输入格式】

输入文件的第一行包括 3 个正整数 N，L，R。

第二行包括 N 个数，按顺序依次表示序列 A 的每一项。

【输出格式】

输出文件包括一行，一个实数，保留 4 位小数，表示答案。

【样例输入】

3 2 3

6 2 8

【样例输出】

5.3333

【数据规模与约定】

20%的数据满足，1 <= N <= 200.

40%的数据满足，1 <= N <= 2 000.

100%的数据满足，1 <= N <= 20 000, 1 <= L <= R <= N, 0 <= Ai <= 1 000 000.

【来源】

HZOI 2016

此题有一个关键，用前缀和维护区间之值，然后在暴力是，先将最大区间和选出，在除以区间数的个数，除法运算很慢，尽量少用；

T4点：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<iostream>
 4 #define ll long long
 5 
 6 using namespace std;
 7 const int N=20010;
 8 
 9 ll a[N];
10 ll s[N];
11 
12 inline void read(ll &x)
13 {
14     char c=getchar();
15     x=0;
16     while(c<'0'||c>'9')c=getchar();
17     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
18 }
19 
20 int main()
21 {
22     freopen("bestseq.in","r",stdin);
23     freopen("bestseq.out","w",stdout);
24     ll n,l,r;
25     read(n);
26     read(l);
27     read(r);
28     read(a[1]);
29     s[1]=a[1];
30     for(int i=2;i<=n;i++)
31     {
32         read(a[i]);
33         s[i]=a[i]+s[i-1];
34     }
35     double Answer=0;
36     for(int i=l;i<=r;i++)
37     {
38         for(int j=1;j<=n-i+1;j++)
39         {
40             Answer=max(Answer,double((double)(s[j+i-1]-s[j-1])/(double)(i)));
41         }
42     }
43     printf("%.4lf",Answer);
44     return 0;
45 }

AC：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<iostream>
 4 #define ll long long
 5 
 6 using namespace std;
 7 const int N=20010;
 8 
 9 ll a[N];
10 ll s[N];
11 
12 inline void read(ll &x)
13 {
14     char c=getchar();
15     x=0;
16     while(c<'0'||c>'9')c=getchar();
17     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
18 }
19 
20 int main()
21 {
22     freopen("bestseq.in","r",stdin);
23     freopen("bestseq.out","w",stdout);
24     ll n,l,r;
25     read(n);
26     read(l);
27     read(r);
28     read(a[1]);
29     s[1]=a[1];
30     for(int i=2;i<=n;i++)
31     {
32         read(a[i]);
33         s[i]=a[i]+s[i-1];
34     }
35     if(n>3000 && r-l>40)r=min(r,l+80);
36     double Answer=0;
37     double ANS=0;
38     for(int i=l;i<=r;i++)
39     {
40         for(int j=1;j<=n-i+1;j++)
41         {
42             Answer=max(Answer,double(s[j+i-1]-s[j-1]));
43         }
44         ANS=max(ANS,Answer/i);
45     }
46     printf("%.4lf",ANS);
47     return 0;
48 }