万万没想到之二分法（Best Cow Fences、讲得就很透彻，就很舒服）

ゝ一世哀愁。 2022-12-19 13:13 318阅读 0赞

### [Best Cow Fences][] ###

【文章中的子串实际上是字段，手误了】  
题意：给定一个正整数数列A , 求一个平均数最大,长度不小于 L 的子串。  
（想不到这种题目也可以用二分来解答，菜是原罪哎）

方法一：枚举暴力法

#include<bits/stdc++.h>
    using namespace std;
    int sum[100010];
    int main(){ 
    	int n, l;
    	memset(sum, 0, sizeof(sum));
    	scanf("%d%d", &n, &l);
    	for(int i=1; i<=n; i++){ 
    		int tmp;
    		scanf("%d", &tmp);
    		sum[i] = sum[i-1]+tmp;
    	}
    	double ans = 0;
    	for(int i=l; i<=n; i++){ 		//结尾
    		for(int j=0; j+i<=n; j++){ 	//开头
    			ans = max((double)(sum[i+j]-sum[j])/i, ans);
    		}
    	}
    	printf("%d\n", (int)(ans*1000));
    	
    	return 0;
    }

--------------------

方法二：二分查询  
请让我慢慢分析其中秘密…

#### 解题思路 ####

手工代码思路（排版有点醉）  
![流程图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
**①、平均值区间。**  
其实我们观察题目可以发现平均数的取值范围只有\[0, 2000\]，那我们初始化左指针 l = 0.0，右指针 r = 2000.0 进行二分 mid = ( l+r )/2 即可。  
sum 数组为 a 数组的前缀和

**②、判断 mid 作为平均值是偏大或偏小。（难点）**  
sum\_pj 数组：每个数减去平均值 mid 的前缀和。  
例如 sum\_pj\[5\] = sum\[5\] - 5 \* mid  
（下标从 1 开始）

通过 ans = max(sum\_pjL<=i<=n \- min(sum\_pj0<=j<=n-L)

double ans=-INF, mi = INF;
    	for(int i=L; i<=n; i++){ 
    		mi = min(mi, sum_pj[i-L]);
    		ans = max(ans, sum_pj[i]-mi);
    	}

#### 问题转化 ####

**在 a 数组上求一个平均数最大且长度不小于 L 的子串**，转化为**在 sum\_pj 数组上求长度不小于 L 的最大子串**。  
因为 ans 始终维护的是最大的情况，所以当 ans == 0 时，mid 恰好等于 a 数组的最大平均值。

实现代码

#include<iostream>
    #define INF 1>>30
    using namespace std;
    int a[100010], n, L;
    double sum_pj[100010], sum[100010];
    
    //假设 mid 为平均值 
    bool judge(double mid){ 
    	sum_pj[0]=0;
    	
    	for(int i=1; i<=n; i++)
    		sum_pj[i] = sum[i] - i*mid;
    	
    	//ans：a 数组减去平均数后长度大于等于 L 的最大子序和
    	double ans=-INF, mi = INF;
    	for(int i=L; i<=n; i++){ 
    		mi = min(mi, sum_pj[i-L]);
    		ans = max(ans, sum_pj[i]-mi);
    	}
    	
    	return ans>=0;
    }
    
    
    int main(){ 
    	scanf("%d%d", &n, &L);
    	
    	for(int i=1; i<=n; i++)
    		scanf("%d", &a[i]);
    		
    	sum[0]=0;
    	for(int i=1; i<=n; i++)
    		sum[i] = sum[i-1]+a[i];
    		
    	double l=0.0, r=2000.0;
    	while(r-l>1e-5){ 
    		double mid = (l+r)/2;
    		if(judge(mid))
    			l = mid;
    		else
    			r = mid;
    	}
    	printf("%d", int(r*1000));
    	
    	return 0;
    }

[Best Cow Fences]: https://vjudge.net/problem/POJ-2018
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/32d734d7004e4bbcb3a7dc1401b0910f.png