论文题,再度认识了数形结合!!!所谓斜率判断时,可以划分阴影区域的,有助于判断
#include<iostream> #include<algorithm> #include<queue> #include<deque> #include<vector> #include<functional> using namespace std; inline int read(){ char c=getchar(); int x=0,f=1; while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*f; } const int max_n = 1e5+100; int a[max_n]; double sum[max_n]; int n,k; double fix(int i,int j){ return (sum[i]-sum[j])/(i-j); } bool check(int a,int b,int c){ return fix(a,c)<=fix(b,c); } bool check2(int a,int b,int c){ return fix(a,c)<=fix(a,b); } int main(){ while (~scanf("%d %d",&n,&k)){ for (int i=1;i<=n;++i)a[i]=read(); for (int i=1;i<=n;++i)sum[i]=sum[i-1]+(double)a[i]; deque<int> que; double ans = 0; for (int i=k;i<=n;++i){ while (que.size()>=2&&check2(que[que.size()-1],que[que.size()-2],i-k)) que.pop_back(); que.push_back(i-k); while (que.size()>=2&&check(que[0],que[1],i)) que.pop_front(); ans = max(ans,fix(i,que.front())); }printf("%.2lf\n",ans); } }