洛谷1419 寻找段落（单调队列）

洛谷1419 寻找段落

本题地址： http://www.luogu.org/problem/show?pid=1419

题目描述

给定一个长度为n的序列a_i,定义a[i]为第i个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在[S,T]之间的连续序列。最有价值段落是指平均值最大的段落，
段落的平均值=段落总价值/段落长度。

输入输出格式

输入格式：

第一行一个整数n，表示序列长度。
第二行两个整数S和T，表示段落长度的范围，在[S,T]之间。
第三行到第n+2行，每行一个整数表示每个元素的价值指数。

输出格式：

一个实数，保留3位小数，表示最优段落的平均值。

输入输出样例

输入样例#1：

2 2

-1

输出样例#1：

1.000

说明

【数据范围】
对于30%的数据有n<=1000。
对于100%的数据有n<=100000,1<=S<=T<=n，-10000<=价值指数<=10000。
【题目来源】
tinylic改编

【思路】

二分+单调队列。

首先二分最大平均值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<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 const int maxn = 100000+10;
 7 
 8 int A[maxn];
 9 int n,s,t;
10 
11 double sum[maxn];
12 int q[maxn],front,rear;
13 bool can(double x) {
14     sum[0]=0;
15     for(int i=1;i<=n;i++) sum[i] = sum[i-1]+A[i]-x;
16     front=1; rear=0;                  //初始化单调队列为空 
17     for (int i = 1; i <= n; i++) {  
18         if (i >= s) {                 //足够s个  //front为在i-t..i-s区间内的最小值
19             while (rear >= front && sum[i - s] < sum[q[rear]])  rear--;  
20             q[++rear] = i - s;        //入队区间起点-1 
21         }
22         if (front <= rear && q[front] < i - t) front++;  //维护区间i-t  
23         if (front <= rear && sum[i] - sum[q[front]] >= 0) return true; //有大于0的区间和说明最大平均值还可以更大   
24     }
25     return false;
26 }
27 
28 int main() {
29     scanf("%d%d%d",&n,&s,&t);
30     double L=0,R=0;
31     for(int i=1;i<=n;i++) scanf("%d",&A[i]) , R=max(R,(double)A[i]);
32     while(R-L>1e-4) {
33         double M=L+(R-L)/2;
34         if(can(M)) L=M;
35         else R=M;
36     }
37     printf("%.3lf
",L);                                            
38     return 0;
39 }