区间最大平均值

题目链接：https://www.luogu.com.cn/problem/P1404

题目描述：

给一个长度为 n 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度≥m。 

输入格式：

第一行两个整数 n 和 m。

接下来 n 行，每行一个整数 ai，表示序列第 i个数字。

输出格式：

一个整数，表示最大平均数的 1000倍，如果末尾有小数，直接舍去，不要用四舍五入求整。

输入样例：

10 6

6

4

2

10

3

8

5

9

4

1

输出样例：6500

数据规模与约定

• 对于60% 的数据，保证 m≤n≤10^4；
• 对于100% 的数据，保证 1≤m≤n≤10^5，0≤ai​≤2000。

  ---

涉及知识 ：前缀法、二分查找 

前缀法

#include<bits/stdc++.h>
using namespace std;
int sum[105],a[105];
int main(){
	int i,n;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];//sum[i]为前i个数组的前缀和 
	}
	for(i=1;i<=n;i++)
	printf("%d ",sum[i]); 
	return 0;
} 

 二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

时间复杂度 O(log2n)

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,i,l,r,x,mid;//查找x 
	int a[105]; 
	scanf("%d %d",&n,&x);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	l=1;r=n;
	while(l!=r){
		mid=(l+r+1)/2;
		if(a[mid]<=x){//如果比中间值大就向右找，否则向左找
			l=mid;
		}else{
			r=mid-1;
		}
	}
	printf("%d\n",l);//输出下标 
	return 0;
} 

思路

本题思路就是先假设一个固定值A，使最大平均值一定大于等于这个固定值

所以这个固定值一定在序列最大值和最小值之间

在序列中存在一段 ai+...+aj 的平均值大于等于A,就相当于 (ai-A)+...+(aj-A) 的平均值大于等于0 ，即 (ai-A)+...+(aj-A) >=0

令 bi=ai-A，问题变成区间求和  bi+...+bj>=0,相当于求前缀和

具体代码如下

#include<bits/stdc++.h>
using namespace std;
#define MAX 2000010
#define ll long long
ll n,m,mid,l,r;
ll a[MAX],b[MAX],sum[MAX];
ll check(ll x){
    for(ll i=1;i<=n;i++){
        b[i]=a[i]-x;//a[i]减掉mid 
        sum[i]=sum[i-1]+b[i];//sum[i]为a[i]减掉mid的前缀和 
    }
    ll y=MAX;
    for(ll i=m;i<=n;i++) {//长度至少为m 
        y=min(y,sum[i-m]);
        if(sum[i]-y>=0) return 1; //平均值是否大于mid 
    }
    return 0;
}
int main(){
    scanf("%lld %lld",&n,&m);
    l=MAX,r=0;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i]*=1000;
		l=min(l,a[i]);
		r=max(r,a[i]);
		//找到最小值和最大值，最大平均值一定在这之间
	}
    while(l!=r){
        mid=(l+r+1)/2;
        if(check(mid))
			l=mid;//平均值小了扩大 
        else 
			r=mid-1;//平均值大了缩小 
    }
    printf("%lld\n",l); 
    return 0;
}
//洛谷 P1404平均数
//n个元素求长度大于等于m的连续子序列的最大平均值 
//输出：一个整数，表示最大平均数的 1000倍，如果末尾有小数，直接舍去，不要用四舍五入求整

题目链接：https://ac.nowcoder.com/acm/contest/11255/J

题目大意是定义一个矩阵 ,找一个子矩阵宽度至少x，长度至少y，求子矩阵的最大平均值

问题转化成 : 找 a 的一个长度至少为 x 的平均值最大的子区间和 b 的一个长度至少为 y 的平均值最大的子区间，就是对分别对 a 和 b 对应的区间求个平均值然后加起来

代码实现

#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
#define ll long long
int n,m,p,q;
double a[MAX],b[MAX],c[MAX],d[MAX],sum[MAX];
double l1,l2,r1,r2;
int check1(double x){
    for(int i=1;i<=n;i++){
        c[i]=a[i]-x;
        sum[i]=sum[i-1]+c[i];
    }
    double y=0x3f3f3f3f;
    for(int i=p;i<=n;i++){
        y=min(y,sum[i-p]);
        if(sum[i]-y>=0) return 1; 
    }
    return 0;
}
int check2(double x){
    for(int i=1;i<=m;i++){
        d[i]=b[i]-x;
        sum[i]=sum[i-1]+d[i];
    }
    double y=0x3f3f3f3f;
    for(int i=q;i<=m;i++){
        y=min(y,sum[i-q]);
        if(sum[i]-y>=0) return 1; 
    }
    return 0;
}
int main(){
    scanf("%lld %lld %lld %lld",&n,&m,&p,&q);
    l1=l2=-1,r1=r2=1e6;
    for (int i=1;i<=n;i++) {
        scanf("%lf",&a[i]);
        l1=min(l1,a[i]);
        r1=max(r1,a[i]);
    }
    for (int i=1;i<=m;i++) {
        scanf("%lf",&b[i]);
        l2=min(l2,b[i]);
        r2=max(r2,b[i]);
    }
    while((r1-l1)>1e-7){
        double mid=(l1+r1)/2.0;
        if (check1(mid)) l1=mid;
        else r1=mid;
    }
    while((r2-l2)>1e-7){
        double mid=(l2+r2)/2.0;
        if (check2(mid)) l2=mid;
        else r2=mid;
    }
    printf("%.10lf\n",l1+l2);//两个数组的最大平均值相加即使区间矩阵的最大平均值 
    return 0;
}