给一个长度为 n 的数列,我们需要找出该数列的一个子串,使得子串平均数最大化,并且子串长度 \ge m。
第一行两个整数 n 和 m。
接下来 n 行,每行一个整数 a_i,表示序列第 i 个数字。
一个整数,表示最大平均数的 1000 倍,如果末尾有小数,直接舍去,不要用四舍五入求整。
10 6
6
4
2
10
3
8
5
9
4
1
6500
显然这是一个“最小值最大”的问题,所以我们要通过二分来枚举平均值,再寻找字段和较大的字段,代入平均值判断是否成立,不成立则将右端向左,成立则将左端向右,使两个端点不断相互逼近最优解即可得到答案。
#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[100001],sum[100001],b[100001];
double eps=1e-5,l=-1e6,r=1e6;
double min(double x,double y){
if(x>y)return y;else return x;
}
double max(double x,double y){
if(x<y)return y;else return x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
cin>>a[i];
}
while(r-l>eps){
double mid = (l+r)/2;
double maxx=-1e10,minn=1e10;
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=m;i<=n;i++){
minn=(double)min(minn,sum[i-m]);
maxx=(double)max(maxx,sum[i]-minn);
}
if(maxx>0)l=mid;else r=mid;
}
cout<<int(r*1000);
return 0;
}
最后修改:2021 年 07 月 05 日 09 : 07 PM
© 允许规范转载