洛谷1419 寻找段落（单调队列+二分）
题目链接:
https://www.luogu.org/problem/show?pid=1419
题意:
题解:
http://www.cnblogs.com/lidaxin/p/4917391.html
二分+单调队列。
首先二分最大平均值x。
那么问题就转化为：是否存在一个区间的的平均值大于x。这个问题可以类比于UVa11090 Going in Cycle!!【见上篇博客】，我们将a全部减去x，问题进一步转化为判断是否存在一个长度在s..t范围内的区间它的和为正，如果有说明还有更大的平均值。
如何判断？单调队列。
令sum表示a-x的前缀和。则上述条件可以变化为sumi-sumj>=0，对于i我们需要找到指定区间内的最小sumj。
单调队列维护序号在i-t到i-s的区间，保持sum的递增序，求区间最大值，判断与0的关系即可。
想了半天！ 蒟蒻想说： 太难了啊！！！
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 const double eps = 1e-6; 18 19 int n,s,t; 20 int a[maxn]; 21 double sum[maxn]; 22 23 // struct node{ 24 // double x; 25 // int y; 26 // }v[maxn]; 27 28 // bool check(double x){ 29 // sum[0]=0; 30 // MS(v); 31 // for(int i=1; i<=n; i++) sum[i] = sum[i-1] + a[i] - x; 32 // int head=1,tail=0; 33 // for(int i=s; i<=n; i++){ 34 // while(head<=tail && sum[i-s]<=v[tail].x) tail--; 35 // tail++; v[tail].x=sum[i-s],v[tail].y=i-s; 36 // while(head<=tail && i-t>v[head].y) head++; 37 // if(head<=tail && sum[i]-v[head].x >= 0) return true; 38 // } 39 // return false; 40 // } 41 int q[maxn],front,rear; 42 bool check(double x) { 43 sum[0]=0; 44 for(int i=1;i<=n;i++) sum[i] = sum[i-1]+a[i]-x; 45 front=1; rear=0; //初始化单调队列为空 46 for (int i = s; i <= n; i++) { 47 if (i >= s) { //足够s个 //front为在i-t..i-s区间内的最小值 48 while (rear >= front && sum[i - s] < sum[q[rear]]) rear--; 49 q[++rear] = i - s; //入队区间起点-1 50 } 51 if (front <= rear && q[front] < i - t) front++; //维护区间i-t 52 if (front <= rear && sum[i] - sum[q[front]] >= 0) return true; //sum[i]-min(sum[i-t~i-s]长度在(s~t)之间) 有大于0的区间和说明最大平均值还可以更大 53 } 54 return false; 55 } 56 int main(){ 57 double L=1e5,R=-1e5; 58 scanf("%d%d%d",&n,&s,&t); 59 for(int i=1; i<=n; i++){ 60 scanf("%d",&a[i]); 61 L = min(L,a[i]*1.0); 62 R = max(R,a[i]*1.0); 63 } 64 65 double ans = 0; 66 while((R-L)>eps){ 67 double mid = (R+L)/2; 68 if(check(mid)) ans=mid,L=mid+eps; 69 else R=mid-eps; 70 } 71 72 printf("%.3lf ",ans); 73 74 75 76 return 0; 77 }