洛谷1419 寻找段落

Posted by yjjr's blog on February 6, 2018

标签:二分,单调队列

题目描述

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

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

输入输出格式

输入格式:

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

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

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

输出格式:

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

输入输出样例

输入样例#1:

3

2 2

3

-1

2

输出样例#1:

1.000

说明

【数据范围】

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

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

 

题意:给定长度为N的序列

求:max{(a[i]+a[i+1]+……+a[i+j])/j}    s<=j<=t

看题的第一眼想到了单调队列,但是貌似会被卡掉TLE

正解是二分答案,判断每次的mid是否可行

Sum[i]表示前i个数减去过去mid的总和

对于第i个数,如果sum[i]>=min{sum[i-y]->sum[i-x]}那么当前方案可行

对于min{sum[i-y]~sum[i-x]},我们用一个单调队列维护就行了

 

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=1e5+6,inf=1e9;
int a[maxn],tt[maxn];
LL c[maxn],sum[maxn];
int n,i,l,r,x,y,mid,ans=0;
inline bool check(int k){
	mem(c,0);mem(tt,0);
	rep(i,1,n)sum[i]=sum[i-1]+a[i]-k;
	int head=1,tail=0;
	rep(i,1,n){
		int j=i-x;
		if(j<0)continue;
		while((sum[j]<c[tail])&&(head<=tail))tail--;
		c[++tail]=sum[j];
		tt[tail]=j;
		if(tt[head]<(i-y))head++;
		if(sum[i]>=c[head])return true;
	}
	return false;
}
int main()
{
    scanf("%d%d%d",&n,&x,&y);
	rep(i,1,n)scanf("%d",&a[i]),a[i]*=1e4;
	l=-inf;r=inf;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid)){l=mid+1;ans=mid;}
		else r=mid-1;
	}
	printf("%.3lf",ans/1e4);
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr