题目大意：

一个数列，求一段长度不少于k的数 使平均值最大

思路：

把所有数列里的数，转换为（i,sum i）的点

然后求一个下凸包，在这个过程中对于长度特殊处理一下，使栈内至少有一段长度大于等于k

下凸包的最后一段即为所求

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #define inf 214748361110 #define ll long long11 #define MAXN 10101012 using namespace std;13 inline int read()14 {15 int x=0,f=1;16 char ch;ch=getchar();17 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}19 return x*f;20 } 21 ll n,l,T;22 ll q[MAXN],s[MAXN],head,tail,ans,x;23 ll cmp(ll x1,ll x2,ll x3,ll x4) { return (s[x2]-s[x1])*(x4-x3)-(s[x4]-s[x3])*(x2-x1);}24 ll gcd(ll a,ll b) { return !b?a:gcd(b,a%b);}25 int main()26 {27 head=tail=0;28 n=read(),l=read();29 for(ll i=1;i<=n;i++)30 x=read(),s[i]=s[i-1]+x;31 ll al=0,ar=l;32 for(ll i=l;i<=n;i++)33 {34 while(head
              
               <0) tail--;35 q[tail++]=i-l;36 while(head
               
                0) head++;37 if(cmp(q[head],i,al,ar)>0||(cmp(q[head],i,al,ar)==0&&(i-q[head]
               
              
             
            
           
          
         
        
       
      

orz bzoj11月赛做出来的唯一一道题