P 1419段落を探す-二分答案+接頭辞と+単調キュー

タイトルリンク
まず問題を読むと、この問題が私たちに求めているのは、長さができるだけ短い場合とできるだけ大きく、二分の答えを考えていることがわかります.
接頭辞和を考慮して、連続シーケンスの和を求めます.
我々が求める平均値がシーケンス内の最大数よりも大きくも最小数よりも小さくもないため,二分の境界を決定することができる.
一方,我々が探しているのは[S,T][S,T][S,T][S,T]の間の最大サブセグメント和であり,単調なキューが容易に考えられるからである.
したがって,二分平均値のたびに接頭辞和を確立し,単調キューで最大のサブセグメント和を求めればよい.
ここでは、読み込み時に各数に1 e 4 1 e 4 1 e 4を乗じ、実数を整数にして処理するのが便利な小さな最適化があります.
コードは次のとおりです.

#include
#define ll long long
using namespace std;
deque <int> q;
int n,s,t,a[100005];
ll sum[100005];
bool check(int x)
{
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]-x;
	while(!q.empty()) q.pop_front();
	int now=0;
	for(int i=s;i<=n;i++)
	{
		while(!q.empty() && sum[q.back()]>sum[now]) q.pop_back();
		q.push_back(now);
		while(q.front()<i-t) q.pop_front();
		if(sum[i]-sum[q.front()]>=0) return 1;
		now++;
	}
	return 0;
}
int main()
{
	int l=2147400000,r=-1000000000;
	scanf("%d %d %d",&n,&s,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]*=10000;
		l=min(l,a[i]);
		r=max(r,a[i]);
	}
	while(l<r)
	{
		int mid=l+r+1 >> 1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	double ans=l*1.0000/10000;
	printf("%.3lf",ans);
	return 0;
}