信息学奥赛一本通 #10012. Best Cow Fences
原题链接
简单
作者:
LLY
,
2021-08-17 09:47:45
,
所有人可见
,
阅读 156
具体题目描述请查看上方链接,必要的注释我已经都写好了
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
/*
* 这题说的是给你一个长度是n的非负整数序列A,然后要求一个平均数最大的,长度不小于L的子段
* 这还是用二分吧,假设手头的二分区间是[L, R],我们要比较mid跟ans的大小
* 如果mid <= ans的话那我应该可以找到一个子段,它的长度 >= L并且平均值 >= mid吧
* 那问题又来了,check函数要怎么写呢?最暴力的方法就是把长度是L, L + 1, ..n的子段全都试过来
* 这样显然是不行的,但是我们可以把所有的a[i]全都减去mid,为什么要这么做呢?
* 如果原先的数组里面有一个子序列的平均数是>= mid的,那就是说存在i跟j
* such that (a[i] + ... a[j]) / (j - i + 1) >= mid and j - i + 1 >= L
* 两边同时乘以(j - i + 1),然后把右边移到左边,就可以一人分配一个mid
* 就有a[i] - mid + a[i + 1] - mid + ... a[j] - mid >= 0
* 所以如果给每个a[i] - mid的话,我们只要找有没有子序列的和是>= 0的就可以了
* 那我们只要找其中最大的看看他是不是>= 0就好了吧
* 这种时候肯定要用前缀和嘛,此时不用更待何时
* 假设b数组满足b[i] = a[i] - mid, sum[i] = b[1] + b[2] + .. b[i]
* 那么我们就是要找max(sum[i] - sum[j - 1]) for all i - j + 1 >= L吧
* 很明显此时的i肯定是>= L的嘛,因此我们可以对i进行从L ~ n的枚举
* 当i固定的时候j肯定只能从1 取到 i - L + 1吧,否则就不满足i - j + 1 >= L了
* 那我肯定是希望j能在这里面取一个使得sum[j - 1]最小的嘛,那难道每次枚举i我们都要重新枚举j从1到i - L?
* 不用的呀,你枚举过j从1到i - L之后把这个值记录下来嘛,然后i变成i + 1的话你多做一次比较就可以了
*/
const int N = 100010;
int a[N], n, length;
double b[N], sum[N];
bool check(double mid) {
for (int i = 1; i <= n; i++) b[i] = a[i] - mid, sum[i] = sum[i - 1] + b[i];
double minimal = 0;
double ans = sum[length];
// ans是用来记录最终的答案的,minimal记录的是我sum[0] ~ sum[i - length]里面的最小值
// 那么如果i = length的话,应该记录的就是sum[0] ~ sum[0]的最小值,这个应该就是sum[0]吧
// 这样就把i = length的情况讨论好了,下面的循环可以直接从length + 1开始
for (int i = length + 1; i <= n; i++) {
/* 假设每一轮循环开始的时候,minimal里面存的都是sum[0] ~ sum[i - 1 - length]里面的最小值
* minimal = min(minimal, sum[i - length])就可以了吧,就可以保证在进入下一轮循环的时候
* minimal里面存的是sum[0] ~ sum[i - length]的最小值了
*/
minimal = min(minimal, sum[i - length]);
ans = max(ans, sum[i] - minimal);
}
return ans >= 0.0;
}
int main() {
scanf_s("%d%d", &n, &length);
for (int i = 1; i <= n; i++) scanf_s("%d", &a[i]);
double L = 0, R = 2000;
while (R - L > 1e-7) {
double mid = (L + R) / 2;
if (check(mid)) L = mid;
else R = mid;
}
printf_s("%d\n", (int)(R * 1000));
}