大佬们求调
查看原帖
大佬们求调
1106289
KomorKomor楼主2024/5/5 17:34
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long 
using namespace std;

double a[100010];
int n,s,t;

bool check(double number)
{
    double max_average;//最有价值段落
    ll q[100010];//模拟算了
    int head=1,tail=0;
    for(int i=1;i<=n;i++)
    {
        while(head<=tail&&a[q[tail]]>=a[i]) tail--;
        q[++tail]=i;
        while(head<=tail&&i-1-q[head]>=t&&i-1-q[head]>=s)   head++;//如果区间长度大于t
        //while(head<=tail&&i-1-q[head]<=t&&i-1-q[head]<=s)   head--;//如果区间长度小于s
        max_average=max(max_average,1.0*(a[i]-a[q[head]])/(i-q[head]+1));
    }
    if(max_average>=number) return true;
    else return false;
}

double bin_search(double l,double r)
{
    double eps=1e-5;
    double ans=-1e9;
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        if(check(mid))//我们希望mid尽可能地大,因此往右边搜
        {
            ans=mid;
            l=mid;
        }
        else r=mid;
    }
    return ans;
}

void solve()
{
    double minn=1e9;
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++)   cin>>a[i],minn=min(minn,a[i]);
    for(int i=1;i<=n;i++)   a[i]=a[i-1]+a[i];    
    printf("%.3lf",bin_search(minn,1e5));
    //下界就是数组中最小的那个数,上界假定一个极大的数字
    //因为n最大为10^5,每个数最大是10^4,因此最大上界就是1e4,扩大一点无所谓
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--)   solve();
    return 0;
}

2024/5/5 17:34
加载中...