P1419

题目

题目描述：

给定一个长度为 nn 的序列 aa，定义 aia_i 为第 ii 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 [S,T][S, T] 之间的连续序列。最有价值段落是指平均值最大的段落。

段落的平均值 等于 段落总价值 除以 段落长度。

输入格式：

第一行一个整数 nn，表示序列长度。

第二行两个整数 SS 和 TT，表示段落长度的范围，在 [S,T][S, T] 之间。

第三行到第 n+2n+2 行，每行一个整数表示每个元素的价值指数。

输出格式：

一个实数，保留 33 位小数，表示最优段落的平均值。

数据范围与说明：

【数据范围】

对于 30%30\% 的数据有 n≤1000n \le 1000。

对于 100%100\% 的数据有 1≤n≤1000001 \le n \le 100000，1≤S≤T≤n1 \le S \le T \le n，−104≤ai≤104-{10}^4 \le a_i \le {10}^4。

【题目来源】

tinylic 改编

输入输出样例 #1

输入：

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

输出：

1
1.000

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
int a[100005];
double b[100005],sum[100005];
int n;
int s,t;
bool check(double x){
    sum[0]=0;
    deque<int> q;
    for(int i=1;i<=n;i++){
        b[i]=(double)a[i]-x;
        sum[i]=sum[i-1]+b[i];
    }
    for(int i=1;i<=n;i++){
        if(i>=s){
            while(!q.empty()&&sum[q.back()]>sum[i-s]){
                q.pop_back();
            }
            q.push_back(i-s);   
        }
        while(!q.empty()&&q.front()<i-t){
            q.pop_front();
        }
        if(!q.empty()&&sum[i]-sum[q.front()]>=0){
             return true;
        }
    }
    return false;
}
int main(){
    cin>>n;
    cin>>s>>t;    
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    double ans;
    double l=-10000,r=10000;
    while(r-l>1e-5){
       double mid=l+(r-l)/2;
        if(check(mid)){
            ans=mid;
            l=mid;
        }else{
            r=mid;
        }
    }
    printf("%.3lf",ans);
    return 0;
}