bzoj 5090 组题

题目大意：

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

思路：

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

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #define inf 2147483611
10 #define ll long long
11 #define MAXN 101010
12 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<tail-1&&cmp(i-l,q[tail-1],i-l,q[tail-2])<0) tail--;
35         q[tail++]=i-l;
36         while(head<tail-1&&cmp(q[head+1],i,q[head],i)>0) head++;
37         if(cmp(q[head],i,al,ar)>0||(cmp(q[head],i,al,ar)==0&&(i-q[head]<ar-al))) al=q[head],ar=i;
38     }
39     ans=s[ar]-s[al];
40     al=ar-al;
41     int g=gcd(abs(ans),al);
42     if(g==al) printf("%lld",ans/al);
43     else printf("%lld/%lld",ans/g,al/g);
44 }

View Code

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