分析

题目要求求一个最大的实数\(x\)，使得某长度在\([S,T]\)之间的区间\([L,R]\)满足

\[\frac{\sum_{i=L}^{R}a_i}{R-L+1}=x
\]

即

\[\sum_{i=L}^{R}a_i=x*(R-L+1)
\]

由于答案满足单调性，所以可以二分\(x\)，转化为判断问题，即判断

\[\sum_{i=L}^{R}a_i\geq x*(R-L+1)
\]

\(\rightarrow\)

\[\sum_{i=L}^{R}\left(a_i-x \right)\geq0
\]

对这个式子求前缀和，就可快速算出一段区间的和，令

\[sum_i=\sum_{i=1}^{i}\left(a_i-x \right)
\]

则区间\([L,R]\)合法的条件为

\[sum_R-sum_{L-1}\geq0
\]

转化成这种形式，已经很好做了。维护一个单增的单调队列，然后判断当前遍历元素是否大于等于队首元素即可。

时间复杂度

假设数据范围为\(A\)，则二分答案是\(O(\log A)\)的，判断一次用了前缀和和单调队列，是\(O(n)\)的，总时间复杂度为\(O(n\log A)\)。

小优化

题目要求保留3位小数，而对浮点数的操作很麻烦，所以不妨对每个数乘10000（多一位是因为要四舍五入），然后算答案时再除10000.0就行了。

用STL的deque实现单调队列，嫌慢手打，使用相同API即可~~（然而这题不卡可以水^_^）~~。

#include<iostream>

#include<cstdio>

#include<deque>

#include<cstring>

#define rg register

template<typename T>inline T read(T&x)

{

	T data=0;

	int w=1;

	char ch=getchar();

	while(ch!='-'&&!isdigit(ch))

		ch=getchar();

	if(ch=='-')

		w=-1,ch=getchar();

	while(isdigit(ch))

		data=data*10+ch-'0',ch=getchar();

	return x=data*w;

}

using namespace std;

typedef long long ll;

const int MAXN=1e5+7;

int n,S,T;

int a[MAXN];

ll sum[MAXN]; // prefix sum

int L=1e8,R=-1e8;

deque <int> Q;

inline bool judge(int x)

{

//	cerr<<"judging x="<<x<<endl;

	memset(sum,0,sizeof(sum));

	for(rg int i=1;i<=n;++i)

	{

		sum[i]=sum[i-1]+a[i]-x;

//		clog<<"sum["<<i<<"]= "<<sum[i]<<endl;

	}

	Q.clear();

	for(rg int i=S,p=0;i<=n;++i,++p)

	{ // 只有一段不包括本身的区间内合法，就开两个扫描线

		while(!Q.empty()&&sum[Q.back()]>sum[p])

			Q.pop_back();

		Q.push_back(p);

		while(Q.front()<i-T) // 这里不用判空是因为p一定存在

			Q.pop_front();

		if(sum[i]-sum[Q.front()]>=0)

			return 1;

	}

//	cerr<<"failed"<<endl;

	return 0;

}

int main()

{

	read(n);read(S);read(T);

	for(rg int i=1;i<=n;++i)

	{

		read(a[i]);

		a[i]*=1e4;

//		cerr<<"a["<<i<<"]= "<<a[i]<<endl;

		L=min(L,a[i]);

		R=max(R,a[i]);

	}

	while(L<R)

	{

		int M=(L+R+1)>>1;

		if(judge(M))

			L=M;

		else

			R=M-1;

	}

	printf("%.3f",L/1e4);

}

Hint

最后说一下单调队列的边界问题。合法区间\([L,R]\)满足

\[S\leq R-L+1\leq T
\]

由于使用前缀和，那么\(i\)，\(p\)应满足

\[S+1\leq i-p+1\leq T+1
\]

也就是说应弹掉\(p<i-T\)的那些点。

还有就是二分答案的边界。求最后一个类型应该int M=(L+R+1)>>1;

巴特西

LG1419 【寻找段落】

分析

时间复杂度

小优化

Hint

最新文章

热门文章