本题第一条题解
📌 变量名说明(均≤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
完全符合样例输出。