单调队列➕二分做不对吗?
查看原帖
单调队列➕二分做不对吗?
1255776
Mr_user楼主2024/1/23 19:57
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e6+3;
double arr[N],ans=0,sum[N];
int n,s,t;
deque<int>du;

int options(int mid){
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+arr[i]-mid;
    int adt=0;
    for(int i=s;i<=n;i++) {
        if(i>t) adt=i-t;
        if(sum[i]-sum[adt]>=sum[du.front()]) return 1;
        while(!du.empty()&&sum[i]<=sum[du.front()]) du.pop_back();
        while(!du.empty()&&i-du.front()>=t) du.pop_front();
        du.emplace_back(i-s+1);
    }
    return 0;
}

signed main(){
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++) cin>>arr[i];
    double l=-1e4,r=1e4;
    while(r-l>=1e-6){
        du.clear();
        du.emplace_back(0);
        double mid=(l+r)/2;
        if(options(mid)){
            ans=mid;
            l=mid+1e-5;
        }
        else r=mid-1e-5;
    }
    printf("%lf\n",ans);
    return 0;
}
2024/1/23 19:57
加载中...