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