洛谷题目链接:平均数
题目描述
给一个长度为n的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度>=m。
输入输出格式
输入格式：
N+1行，
第一行两个整数n和m
接下来n行，每行一个整数a[i],表示序列第i个数字
输出格式：
一个整数，他是最大平均数的1000倍，如果末尾有小数，直接舍去，不要用四舍五入求整。
输入输出样例
输入样例#1：
10 6
6
4
2
10
3
8
5
9
4
1
输出样例#1：
6500
说明
【数据范围】
60% M<=N<=10000
100% M<=N<=100000 0<=a[i]<=2000
一句话题意: 给出一个长度为\(n\)的序列,要求出其中一个长度大于等于\(m\)的子段使得这个子段的平均值最大.
题解: 首先这个平均数是具有单调性的,如果某一个值可以作为最大平均值,那么比它大的值也有可能是平均值,如果某个值经过验证无法成为平均值,那么比这个大的就肯定无法成为平均值.所以可以想到二分.
但是如果要二分的话要怎么验证呢?
我们可以在每次\(check\)中,先将序列中的值都减去二分出来的\(mid\),然后对序列中的值求一个前缀和,再对这个前缀和统计一个最小值.我们用\(S_i\)表示1~ i的前缀和,\(Mn_i\)表示1~i中前缀和的最小值.
这样的话,我们在枚举一个长度大于等于\(m\)的区间\([i,j](j∈[i+m-1,n])\)的时候,这个区间内的和就是\(S_j-S_{i-1}\),但是因为我们已经将这个序列的每个元素都减去了\(mid\),也就相当于这个区间这个区间的平均值减去了\(mid\).这时如果区间和是大于等于0的,也就是说这个区间在没有减去\(mid\)之前它的平均值是大于等于\(mid\)的.
然后通过我们记录的\(Mn\),可以得到1~ i的前缀和的最小值,这样就可以通过固定一个右端点的方法,记录下向左扩展得到最大区间和.如果区间和是正数,那么除以它的个数后还是正数,则存在一个子段使得这个区间的平均值大于等于\(mid\).
然后最后算出来的结果最好是加一个较小的数,因为转int向下取整,有可能会使答案变小,加一个较小的数会被向下取整忽略掉.
#include<bits/stdc++.h>
using namespace std;
const int N=100000+5;
const double eps=1e-5;
const int inf=2147483647;
int n, m, ans = 0;
double a[N], b[N], s[N], mn[N];
int gi(){
int ans = 0, f = 1; char i = getchar();
while(i<'0' || i>'9'){ if(i == '-') f = -1; i = getchar(); }
while(i>='0' && i<='9') ans = ans*10+i-'0', i = getchar();
return ans * f;
}
bool check1(double mid){
memcpy(b, a, sizeof(b));
for(int i=1;i<=n;i++) b[i] -= mid, s[i] = s[i-1]+b[i], mn[i] = min(mn[i-1], s[i]);
for(int i=m;i<=n;i++)
if(s[i]-mn[i-m] > 0) return true;
return false;
}
int main(){
//freopen("cowfnc.in", "r", stdin);
//freopen("cowfnc.out", "w", stdout);
n = gi(), m = gi(); mn[0] = 0;
for(int i=1;i<=n;i++) a[i] = gi();
double l = 0, r = inf, res;
while(r-l > eps){
double mid = (l+r)/2;
if(check1(mid)) res = mid, l = mid;
else r = mid;
}
ans = (res+2e-4)*1000;
cout << ans << endl;
return 0;
}
ps:鸡哥巨佬要我把讲解都删掉,然后膜他
Brave_Cattle sto yyj orz Brave_Cattle