Luogu P1419 寻找段落 题意:要求找出长度在S到T之间段落最大平均值 首先本题可以二分答案转化为判定性问题 如果一个区间有$k$个元素,和为$sum$,平均值$\ge x$ $sum/k \ge x$ $sum-k \times x \ge 0$ 将每一个值都减去$x$,求出$sum$得到$sum \ge 0$ 求出序列每个元素减去$x$后的前缀和 只要知道$i-T$到$i-S$间的最小值,即可求得区间内最大平均值,可使用单调队列维护 如果区间内$i < j < k$,$pre_i>pre_j$,则$pre_k-pre_j>pre_k-pre_i$,$pre_i$已不是最优答案,可以出队 代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include <bits/stdc++.h>
int read() { int a=1,b=0; char c; do{c=getchar(); if(c=='-') a=-1;}while(c<'0'c>'9'); do{b=b*10+c-'0'; c=getchar();}while(c>='0'&&c<='9'); return a*b; }
const int MAXN=100000+100; int num[MAXN];
int N,S,T; double lft,rigt,ans,mid; double pre_sum[MAXN]; std::deque<int> que;
bool judge(double x) { que.clear(); for(int i=1;i<=N;++i){ pre_sum[i]=pre_sum[i-1]+(double)num[i]-x; } for(int i=1;i<=N;++i){ if(i>=S){ while(!que.empty() && pre_sum[que.front()]>pre_sum[i-S]) que.pop_front(); que.push_back(i-S); } if(!que.empty() && que.front()<i-T) que.pop_front(); if(!que.empty() && pre_sum[i]-pre_sum[que.front()]>=0) return true; } return false; }
int main() { N=read(); S=read(); T=read(); for(int i=1;i<=N;++i) num[i]=read(); lft=-10000.0; rigt=10000.0; while(rigt-lft>=1e-5){ mid=(rigt+lft)/2; if(judge(mid)) lft=ans=mid; else rigt=mid; } printf("%.3f\n",ans); return 0; }
|