[暑假集训Day4T1]羊圈

ZYC同志开农场了？？？？？

二分答案。

对于每一个二分出来的答案对其进行检查(check)，检查是否有一个长度大于m的字段和的平均值大于mid。方法如下：先把原数组的每一个元素减去mid，储存进一个新的数组中，我们只需要看这个数组中有没有一段子串和大于0即可（因为都减去了mid，如果大于零加回来后平均值就大于mid了），我们通过一个变量val记录当需要计算的数为i时，前i-m个数的总和最小值（需要的是最大值）。前缀和O(n)统计最大字段和即可。

参考代码如下：

 #pragma GCC optimize(3,"Ofast","inline")

 #include<iostream>

 #include<cstdio>

 #define M 100005

 #define int long long

 #define N 100005

 using namespace std;

 int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-;ch=getchar();}

     return x*f;

 }

 int n,m,a[N],f[N],prefix[N],ans,Min=,Max;

 bool check(int x)

 {

     int val=,ans=-;

     for(int i=;i<=n;i++)f[i]=a[i]-x;

     for(int i=;i<=n;i++)prefix[i]=prefix[i-]+f[i];

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

     {

         val=min(val,prefix[i-m]);

         ans=max(ans,prefix[i]-val);

     }

     if(ans>=)return ;

     else return ;

 }

 signed main()

 {

     n=read();m=read();

     for(int i=;i<=n;i++)a[i]=read(),a[i]*=,Min=min(Min,a[i]),Max=max(Max,a[i]);

     int l=Min,r=Max;

     while(l<=r)

     {

         int mid=l+r>>;

         if(check(mid))l=mid+;

         else r=mid-;

     }

     cout<<l-<<endl;

     return ;

 }

巴特西

[暑假集训Day4T1]羊圈

最新文章

热门文章