详细题解

本题第一条题解

#include<iostream>
#include<vector>
#include<deque>
#include<iomanip>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const double eps=1e-5;
int a[N];
double s[N];
int n,S,T;
bool check(double x){
    for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i]-x;
    deque<int>dq;
    for(int i=S;i<=n;++i){
        int j=i-S;
        while(!dq.empty()&&s[j]<=s[dq.back()])dq.pop_back();
        dq.push_back(j);
        while(!dq.empty()&&dq.front()<i-T)dq.pop_front();
        if(s[i]-s[dq.front()]>=0)return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>S>>T;
    for(int i=1;i<=n;++i)cin>>a[i];
    double l=-1e4,r=1e4;
    while(r-l>eps){
        double m=(l+r)/2;
        if(check(m))l=m;
        else r=m;
    }
    cout<<fixed<<setprecision(3)<<l<<'\n';
    return 0;
}

📌 变量名说明（均≤3字符）
变量名 含义解释
N 最大序列长度（1e5+5）
eps 二分精度（1e-5）
a 存储序列的数组
s 前缀和数组
n 序列长度
S,T 段落长度的范围
l,r,m 二分查找的左右边界和中间值
dq 单调队列
i,j 临时变量，遍历序列
🎯 代码特点
变量名简洁：所有变量名都不超过3个字符
无冗余空格：移除了所有非必要空格
高效算法：时间复杂度O(n log C)，适用于1e5的数据规模，其中C是二分的精度范围
严格按照题目要求：处理所有边界情况，包括负数和大范围数据
正确性保证：通过二分答案+单调队列的方法，准确找到平均值最大的段落
🔧 核心算法逻辑
二分答案：在[-1e4, 1e4]的范围内二分查找可能的平均值
前缀和转换：将每个元素减去当前二分的平均值，计算前缀和
单调队列优化：使用单调队列维护前缀和的最小值，快速判断是否存在满足条件的段落
结果输出：保留三位小数输出最终的最大平均值
📊 测试用例验证
输入#1：

3
2 2
3
-1
2
输出#1：

1.000
完全符合样例输出。