\(二分答案，判断是否存在长度不小于L的字段，平均数不小于二分的值\)
\(如果把数列中每个数都减去二分的值，就转化为判定是否存在一个长度不小于L的子段，子序列和非负\)
\(用前缀和维护数列，就可用O(1)的时间查询平均数\)
\(这题由于精度问题，需要先将读入的数乘上1000再整数二分……乘完之后还要开long long\)
|
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 |
#include<stdio.h> #define MAXN 100010 #define INF 2147483647 #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) > (b) ? (a) : (b)) int n, L, l, r = -INF, a[MAXN]; long long sum[MAXN], b[MAXN]; int main() { scanf("%d%d", &n, &L); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); a[i] *= 1000; r = max(r, a[i]); } while (l <= r) { int mid = (l+r) >> 1; long long x = -INF, ms = INF; for (int i = 1; i <= n; ++i) b[i] = a[i]-mid; for (int i = 1; i <= n; ++i) sum[i] = sum[i-1]+b[i]; for (int i = L; i <= n; ++i) { ms = min(ms, sum[i-L]); x = max(x, sum[i]-ms); } if (x >= 0) l = mid+1; else r = mid-1; } printf("%d", r); return 0; } |