题解 | #Best Cow Fences#

#include<bits/stdc++.h>

using namespace std;

#define int long long 
#define debug printf("++zhangyx++");

const int N = 1e6;
unordered_map<int,int>mp;
double n,m;
double a[N];
double sum[N];

//本人错误的写法
//bool check(double avg)
//{ //个人感觉应该是精度的问题 
//欢迎dalao指点
//不喜可随便pen
//那个 前缀的地方 
//  for(int i=1;i<=n;i++){
   //  for(int j=i+m;j<=n;j++){
  ///       if((sum[j] - sum[i])/(j-i)>=avg) return true;    
  //       } 
  //    }
  //  return false;
//}

bool check(double avg)
{
  for(int i=1;i<=n;i++)
     sum[i] = sum[i-1]+a[i]-avg; //使得每个数都减去avg然后在加起来以判断此时的avg1和avg的大小

     double mins = 0; //其中 i表示右端点 而就j表示左端点
 for(int i = m,j = 0;i<=n;i++,j ++) //这个应该是双指针的奇妙写法 本人不是很懂
  {
     mins = min(mins, sum[j]); // 因为干开始肯定是sum[j] = 0的\
      //然后由于i指针向后动 所以可以更新其最小前缀 然后跟新最大字段 
     //使得j前缀和尽可能小
          //从而使得区间和尽可能的大
     if(sum[i] - mins >= 0) return true; //一旦发现可以>=二分的avg就直接 true
   }

    return false; //如果全部都没有就直接全部退出
}

void solve()
{
      cin >> n >> m;

  for(int i=1;i<=n;i++){
        cin >> a[i];
    // sum[i] = a[i] + sum[i-1];
    // 其实答案的最大值就是最大的a[i]
   }

   double l =0,r = 2*1e6;
     double mid;

      //double型的二分的写法
   while(r-l>1e-6) 
   {
        mid = (l+r)/2;  
     if(check(mid)) l =mid; 
        else r = mid;
   }    

   printf("%d\n",(int)(r*1000));
    //向下取整的写法
}

signed main()
{
   cin.tie(0);    
   cout.tie(0);
 ios::sync_with_stdio(false); 

  int T = 1;//cin >> T;
 while(T--) solve();

   return 0;
}