HDU-2993 二分-至少连续k个平均值最大(数形结合)

题目连接

分析讲解

题意：在n个序列中找出至少k个连续的数，使它们平均值最大，输出最大的值。

题意转化：用sum()求出前n个数的和，那么p=(sum(j)-sum(i-1))/(j-i+1) ,j-i>=k+1;把sum(i)看做y轴的值，i看做x轴的值，由于ai>0;所以图形是：

一条递增的凹凸不平的折线。那么问题就是：在这条折线上找出横坐标的值至少相差k，他们的之间的连线斜率最大。

个人分析：

先以为此题目很容易，没想到自己的算法是暴力枚举O(n^2)，由于数据过大，肯定是过不了的。

听别人说斜率优化！,看了讲解，慢慢弄懂了。

斜率优化有两个重点：

                     1.排除多余的凹点(以下为准)。

                      2.二分找最凸点

排除凹点：

画图就能看出了凹点不可能是去最大值，除了凹点，对结果无影响。把所有的凹点都筛选出来了，留下的当然构成一个递增凸函数。

可以看出，最凸的点排列情况，是一个凸函数，故可以用二分搜索得到！

此题有点坑！时间卡的很厉害，用scanf输入都过不了！

代码：

#include<iostream>
#include<cstdio>typedef __int64 LL;
using namespace std ;struct point{  //用pair可能要快些。int x;LL y;	
}p[100005];int n,k;
LL a[100005];bool cross(point u,point v,point w)
{return (v.x-u.x)*(w.y-v.y)<(v.y-u.y)*(w.x-v.x);
}inline int search(int l,int r,point G)
{int mid;while(l<r){mid=(l+r)>>1;if(cross(p[mid],p[mid+1],G)) r=mid;else l=mid+1;}return l;
}double solve()
{double Max=-1;int cnt=0;point L,R;for(int i=k;i<=n;i++){L.x=i-k,L.y=a[i-k];R.x=i,R.y=a[i];while(cnt>1&&cross(p[cnt-1],p[cnt],L)) cnt--;p[++cnt]=L;int o=search(1,cnt,R);double ans=(double)(a[i]-p[o].y)/(i-p[o].x);if(ans>Max) Max=ans;}return Max;
}inline int input()
{char ch=' ';while(ch<'0'||ch>'9')ch=getchar();int x=0;while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();return x;
}int main()
{while(scanf("%d %d",&n,&k)!=EOF){a[0]=0;for(int i=1;i<=n;i++){a[i]=(LL)input();a[i]+=a[i-1];}printf("%.2lf\n",solve());}return 0 ;
}