P1419 寻找段落

题目描述

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

段落的平均值=段落总价值/段落长度。

输入输出格式

输入格式：

第一行一个整数n，表示序列长度。

第二行两个整数S和T，表示段落长度的范围，在[S,T]之间。

第三行到第n+2行，每行一个整数表示每个元素的价值指数。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

1.000

说明

【数据范围】

对于30%的数据有n<=1000。

对于100%的数据有n<=100000,1<=S<=T<=n，-10000<=价值指数<=10000。

【题目来源】

tinylic改编

Solution:

　　本题比较套路，写了Poj2823+Luogu1404后不难得到本题做法：二分答案+分数规划+单调队列。

　　二分一下答案，然后分数规划处理出前缀和，等价于判断是否存在一段长度在限制范围内的和大于$0$。而当我们确定了右端点$i$后，左端点$j$所在范围也会被确定在一个区间内，然后贪心的想到只需判断$sum[i]-min(sum[j]),j\in[i-t+1,i-s+1]$是否大于等于$0$，对于$sum[j]$不难发现取值范围的长度固定且每次$i$右移只会引起左右边界相应的移动，很显然可以尺取法用单调队列维护最小值，这样每次$check$就是$O(n)$的了。

代码：

#include<bits/stdc++.h>

#define il inline

#define ll long long

#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)

using namespace std;

const int N=;

int n,S,T,q[N];

double a[N],b[N],s[N];

il int gi(){

    int a=;char x=getchar();bool f=;

    while((x<''||x>'')&&x!='-')x=getchar();

    if(x=='-')x=getchar(),f=;

    while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();

    return f?-a:a;

}

int main(){

    n=gi(),S=gi(),T=gi();

    For(i,,n) a[i]=gi();

    double l=-,r=,mid;

    while(r-l>1e-){

        mid=(l+r)/;

        For(i,,n) b[i]=a[i]-mid,s[i]=s[i-]+b[i];

        int hd=,ed=,f=;

        For(i,S,n) {

            while(hd<=ed&&s[i-S]<s[q[ed]])ed--;q[++ed]=i-S;

            if(hd<=ed&&q[hd]<i-T) hd++;

            if(hd<=ed&&s[i]-s[q[hd]]>=) {f=;break;}

        }

        f?(l=mid):(r=mid);

    }

    printf("%.3lf",r);

    return ;

}

巴特西

P1419 寻找段落

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章