P1404 平均数

题目描述

给一个长度为nn的数列,我们需要找出该数列的一个子串,使得子串平均数最大化,并且子串长度>=m>=m

输入格式

N+1N+1行,

第一行两个整数nnmm

接下来nn行,每行一个整数a[i]a[i],表示序列第ii个数字

输出格式

一个整数,他是最大平均数的10001000倍,如果末尾有小数,直接舍去,不要用四舍五入求整。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
9
10
11
10 6
6
4
2
10
3
8
5
9
4
1

输出 #1

1
6500

说明/提示

【数据范围】

6060% M<=N<=10000

100100% M<=N<=100000 0<=a[i]<=2000

思路

想了很久!!!!

我就是一个sb!!!!

直接二分答案平均数,验证。

验证怎么做呢?非常巧妙的方法。

将每一个数都减去二分答案出来的平均数,然后计算前缀和,将问题转化为“寻找一个长度不小于mm的数列,使之数列中数字的和大于等于00”。

很容易看出,子串的右端点rr的范围为[m,n][m,n],则左端点ll的范围为[1,rm+1][1,r-m+1]

我们可以很巧妙的得到一个结论:当我们知道右端点,就可以得到左端点的范围。

so,

我们只需要枚举右端点,判断sum[r]min(sum[l1]),l[1,rm+1]sum[r]-min(sum[l-1]),l\in[1,r-m+1]是否大于等于00即可。

所以我们记录下来可选的左端点的最小值,进行判断即可。

1
2
3
4
5
Min=std::min(Min,fsum[i-m]);
if(fsum[i]-Min>=0){
f=true;
break ;
}

code

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<iostream>

#define int long long
const int maxn=1e5+10;

int n,m,l,r,a[maxn],fsum[maxn];
bool f;

inline int read(){
char ch=getchar();int f=1,r=0;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){r=r*10+ch-'0';ch=getchar();}
return f*r;
}

signed main(){
n=read(),m=read();
for(register int i=1;i<=n;i++){
a[i]=read()*10000;
r=std::max(a[i],r);
}
while(l<r){
int mid=(l+r)>>1,Min=0;
for(register int i=1;i<=n;i++){
fsum[i]=fsum[i-1]+a[i]-mid;
if(i>=m){
Min=std::min(Min,fsum[i-m]);
if(fsum[i]-Min>=0){
f=true;
break ;
}
}
}
if(f) l=mid+1;
else r=mid;
f=false;
}
int mid=l,Min=0;
for(register int i=1;i<=n;i++){//防止mid才是答案
fsum[i]=fsum[i-1]+a[i]-mid;
if(i>=m){
Min=std::min(Min,fsum[i-m]);
if(fsum[i]-Min>=0){
f=true;
break ;
}
}
}
if(!f) l=mid-1;
printf("%lld",l/10);
return 0;
}
文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/08/16/P1404 平均数/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论