1.4.6 Best Cow Fences(solution+discuss)

大家好，这又是一道二分题，首先来看题面。

Description

Farmer John's farm consists of a long row of NNN ( 1≤N≤1051 \le N \le 10^51≤N≤105)fields. Each field contains a certain number of cows, 1≤ncows≤20001 \le ncows \le 20001≤ncows≤2000.

FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block.

The block must contain at least FFF (1≤F≤N1 \le F \le N1≤F≤N) fields, where FFF given as input.

Calculate the fence placement that maximizes the average, given the constraint.

给定正整数数列A，求一个平均数最大的，长度不小于L的(连续的) 子段。

Input

• Line 1: Two space-separated integers, NNN and FFF.

• Lines 222..N+1N+1N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on.

Output

• Line 1:A single integer that is  1000  \;1000\;1000times the maximal average.Do not perform rounding, just print the integer that is 1000×ncows/n1000\times ncows/n1000×ncows/n fields.

Sample Input 1

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

Sample Output 1

6500 

Hint

1  ≤  N  ≤  100,0001  \le  N  \le  100,0001  ≤  N  ≤  100,000

1  ≤  ncows  ≤  20001  \le  ncows  \le  20001  ≤  ncows  ≤  2000

  

   

    

     

    
    

     

      #include<bits/stdc++.h>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      int n,f;
     
    
   

    

     

    
    

     

      double line[100010];//正整数数列A 
     
    
   

    

     

    
    

     

      double sum[100010];//前缀和 
     
    
   

    

     

    
    

     

      double b[100010];//储存数列A减去当前数值
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

      题解：对平均数进行二分，找出减去当前平均数的前缀和sum[i]-min_val的值得到答案ans来判断可否实现。-Megumin
     
    
   

    

     

    
    

     

      */
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	scanf("%d %d", &n, &f);
     
    
   

    

     

    
    

     
	for (int i = 1; i <= n; i++) 
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		scanf("%lf", &line[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	double eps = 1e-5;
     
    
   

    

     

    
    

     
	double l = -1e6, r = 1e6;
     
    
   

    

     

    
    

     
	while(r-l > eps)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		double mid = (l+r) / 2;
     
    
   

    

     

    
    

     
		for (int i = 1; i <= n; i++) 
     
    
   

    

     

    
    

     

      			b[i] = line[i] - mid;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		for (int i = 1; i <= n; i++) 
     
    
   

    

     

    
    

     

      			sum[i]=sum[i-1]+b[i];//obj 1前缀和处理 
     
    
   

    

     

    
    

     
		//以下是记录 
     
    
   

    

     

    
    

     
		double ans = -1e10;//保存当前的答案 
     
    
   

    

     

    
    

     
		double min_val = 1e10;//保存当前的前缀和最小值
     
    
   

    

     

    
    

     
		for (int i = f; i <= n; i++) 
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			min_val = min(min_val, sum[i - f]);//obj 2当处理i的时候我们最短可以减掉哪里的sum值？ 
     
    
   

    

     

    
    

     

      			ans = max(ans, sum[i] - min_val);//obj 3答案是怎么算出来的？ 
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
     
    
   

    

     

    
    

     
		if(ans>=0)//obj 4二分处理 
     
    
   

    

     

    
    

     

      			l=mid; 
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      			r=mid;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("%d",(int)(r*1000));
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

需要思考三个问题：

1、

  

   

    

     

    
    

     

      for (int i = 1; i <= n; i++) 
     
    
   

    

     

    
    

     

      			sum[i]=sum[i-1]+b[i];//obj 1前缀和处理 
     
    
   

    

     

    
    

     
		//以下是记录 
     
    
   

    

     

    
    

     
		double ans = -1e10;//保存当前的答案 
     
    
   

    

     

    
    

     
		double min_val = 1e10;//保存当前的前缀和最小值
     
    
   

    

     

    
    

     
		for (int i = f; i <= n; i++) 
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			min_val = min(min_val, sum[i - f]);//obj 2当处理i的时候我们最短可以减掉哪里的sum值？ 
     
    
   

    

     

    
    

     

      			ans = max(ans, sum[i] - min_val);//obj 3答案是怎么算出来的？ 
     
    
   

    

     

    
    

     

      		}
     
    
  
 

这里sum[i-1]+b[i]是想干什么？b[i]是干什么用的？

2、

  

   

    

     

    
    

     
		if(ans>=0)//obj 4二分处理 
     
    
   

    

     

    
    

     

      			l=mid; 
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      			r=mid;
     
    
  
 

l,r在二分的时候为什么不用加一or减一？

 想了解详情，笔者之后会更新，请您多多关注~

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120583656