11月总结

题目链接：https://www.luogu.com.cn/problem/P1419题目大意给定一个长度为 n 的整数序列 a，以及两个整数 S 和 T。要求在所有长度在区间 [S, T] 内的连续子数组中，找出平均值最大的那个，并输出其平均值（保留三位小数）。解题思路1. 暴力法不可行若直接枚举所有满足长度在 [S, T] 范围内的子数组，时间复杂度为：O(n * (T - S + 1))约等于 O(n^2)对于 n = 10^5 来说显然会超时。2. 二分答案 + 单调队列优化我们考虑使用 二分答案 的思想：我们可以构造新数组 bi = i - mid，然后判断是否存在长度在 [S, T...