AcWing. 102 best cattle fence

Topic link

Title Description

Farmer John's farm is owned by N Fields make up , There are a certain number of cattle in every field , No less than 1 head , Not more than 2000 head .

John wants to fence a part of the continuous field , And make the average number of cattle contained in each piece of land in the enclosed area reach the maximum .

The enclosed area shall at least contain F Block plot , among F It will give .

Under the given conditions , Calculate the average of the number of cattle contained in each piece of land in the enclosed area, what is the maximum possible value .

Input format
Enter the integer in the first line N and F, Data is separated by spaces .

Next N That's ok , Enter an integer for each line , The first i+1 The integer entered on the line represents the number i The number of cattle included in the slice area .

Output format
Output an integer , Represents the maximum value of the average multiplied by 1000 Again Rounding down And then the results .

Data range
$1\le N\le 100000$
$1\le F\le N$

 sample input ：
10 6
6 
4
2
10
3
8
5
9
4
1

 sample output ：
6500

---

Using double pointers or greed is wrong , It is not monotonous .
such as : [4, 3, 2, 1, 9]F = 3
With 1 The maximum at the end is : [4, 3, 2, 1] = 2.5
With 9 The biggest thing at the end is : [2, 1, 9] = 4

Here is 3 individual , It's not monotonous !
[4, 3, 2, 1, 9] = 3.8
[3, 2, 1, 9] = 3.7
[2, 1, 9] = 4

---

The key is : $\frac{S[r]-S[l]}{r-l}=ans$, ans Of course it's unknown , Even if you are fixed r after , One more l, It's also unknown !

so , Think of two points , Dichotomy can take one of the variables ans, Become constant .

---

and , notice Maximum or Minimum , You should go to Two points Think about it !

1, Define a binary domain D by : All possible averages , [1, 2000] The real number

2, Definition Calc( x) by : All legal intervals ( The length of the >=F The range of ) in , Is there an average >= x The range of .

$$\begin{gathered} Whether\; there\; is\; an\; interval‘[l+1,r]‘,Its\; average\; value,namely(\frac{S[r]-S[l]}{r-l}),yes\ge xOf \\ namely\frac{S[r]-S[l]}{r-l}>=x,Simplification:{\sum }_{i=l+1}^{r}A[i]\ge (r-l)\ast x \\ {\sum }_{i=l+1}^r(A[i]-x)\ge 0 \end{gathered}$$

namely , structure : B[i] = A[i] - x, Find whether there is continuous length >= F The range of , The sum is >=0 Of , This can be done by : The prefix and + Linear scanning achieves .

Calc( x) = true, x <= ans
Calc( x) = false, x > ans
Conform to Boolean duality .

Code

bool Check( double _avg){
    
    S[ 0] = double( A[ 0]) - _avg;
    FOR_( i, 1, N-1, 1){
    
        S[ i] = S[ i - 1] + double( A[ i]) - _avg;
    }
    double ma = S[ Len - 1];
    double pre_min = 0;
    //< pre_min Must be 0,  It cannot be an illegal value .  such as : [1, 0, 1, 0], Len=3
    //< S[3] yes 0,  explain :  The sum of the first four is 0.  namely , pre_min yes 0,  Description is the whole prefix 
    FOR_( i, Len, N-1, 1){
    
        pre_min = min( pre_min, S[ i - Len]);
        ma = max( ma, S[ i] - pre_min);
    }
    return ma >= 0;
}

void __Solve(){
    
    scanf("%d%d", &N, &Len);
    FOR_( i, 0, N-1, 1){
    
        scanf("%d", &A[ i]);
    }
    double l = 1, r = 2000;
    constexpr double Eps_ = 1e-8;
    while( r - l > Eps_){
    
        double mid = (l + r) / 2;
        if( Check( mid)){
    
            l = mid;
        }
        else{
    
            r = mid;
        }
    }
    printf("%d", int( r * 1000.0)); //<  Must be r,  the reason being that ( Round down )