P1419 寻找段落 实数二分答案 + 单调队列
作者:
多米尼克領主的致意
,
2024-05-04 19:05:00
,
所有人可见
,
阅读 2
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-7;
int s, t;
int n;
double a[N], sum[N];
bool check(double x)
{
for(int i = 1;i <= n;i++)
{
sum[i] = sum[i - 1] + a[i] - x;
}
deque<int>q;
for(int i = s;i <= n;i++)
{
while(q.size() && sum[i - s] < sum[q.back()])q.pop_back();
q.push_back(i - s);//sum[r] - sum[l - 1];
while(q.size() && i - q.front() > t)q.pop_front();
if(q.size() && sum[i] - sum[q.front()] > 0)return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
cin >> s >> t;
for(int i = 1;i <= n;i++)cin >> a[i];
double l = -10000, r = 10000;
while(r - l > eps)
{
double mid = (l + r) / 2.0;
if(check(mid))l = mid;
else r = mid;
// cout << l << endl;
}
printf("%.3f", l);
return 0;
}