传送门

Description

给出包含一个N个整数的数组A。找出一段长度至少为K的连续序列，最大化它的平均值。
请注意：一段子序列的平均值是子序列中所有数的和除以它的长度。

Input

第一行包含两个整数N(1<=N<=300000)，K(1<=K<=N)。
第二行包含N个整数，代表数组A，1<=ai<=10^6。

Output

一行一个实数，代表最大的平均值。允许在0.001以内的绝对误差。

Sample Input

1
2
3
4
5
6
7
8
9
输入1：
4 1
1 2 3 4
输入2：
4 2
2 4 3 4
输入3：
6 3
7 1 2 1 3 6

Sample Output

1
2
3
4
5
6
输出1：
4.000000
输出2：
3.666666
输出3：
3.333333

Data Constraint

对于30%的数据，N<=5000。
对于100%的数据，1<=N<=300000, 1<=K<=N, 1<=Ai<=1000000。

题解

看到最大化最小化之类的想到就是二分答案

设二分出来的平均值为ansans​，辣么

(∑i=lrai)÷(i−j)≥ans∑i=lrai≥ans×(i−j)∑i=lrai−ans×(i−j)≥0∑i=lr(ai−ans)≥0(\sum_{i=l}^{r} a_i) \div (i-j) \ge ans \\ \sum_{i=l}^{r} a_i \ge ans \times (i-j) \\ \sum_{i=l}^{r} a_i - ans \times (i-j) \ge 0 \\ \sum_{i=l}^{r} (a_i-ans) \ge 0 \\

如果用sumsum数组维护前缀和的话，那柿子就会变成酱紫

∵sumi=sumi−1+ai−ans∴sumr−suml−1≥0∴如果sumr≥suml−1那么ans成立，反之不成立\because sum_i = sum_{i-1} + a_i - ans \\ \therefore sum_r - sum_{l-1} \ge 0 \\ \therefore 如果 sum_r \ge sum_{l-1} \\ 那么 ans 成立，反之不成立

所以说，我们只需要最小化suml−1sum_{l-1}即可

checkcheck的时间复杂度为O(n)O(n)

二分的时间复杂度为O(log n)O(log \, n)​

综上，本代码时间复杂度为O(n log n)O(n \, log \, n)​

代码

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 <cstdio>
#define N 300005
#define min(x,y) (((x)<(y))?(x):(y))
#define fre(x) freopen(#x".in","r",stdin),\
	freopen(#x".out","w",stdout)
using namespace std;
double mn[N],sum[N];
int n,k,a[N];
bool check(double ave)
{
	mn[0]=0x3f3f3f3f;
	for (int i=1;i<=n;++i)
		sum[i]=sum[i-1]+a[i]-ave,
			mn[i]=min(mn[i-1],sum[i]);
	for (int i=k;i<=n;++i)
		if (sum[i]>=mn[i-k]) return 1;
	return 0;
}
int main()
{
	fre(average);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i)
		scanf("%d",a+i);
	double l=1,r=1000000;
	while (r-l>=0.000001) {
		double mid=(l+r)/2.0;
		if (check(mid)) l=mid;
		else r=mid-0.000001;
	}printf("%.6lf",l);
}

完结撒花！♪(＾∀＾●)ﾉ