大佬们求调
查看原帖
大佬们求调
1106289
KomorKomor楼主2024/5/5 18:09
#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++)
    {
        if(i>=s)
        {
            while(head<=tail&&a[q[tail]]>=a[i-s]) tail--;
            q[++tail]=i-s;
        }
        while(head<=tail&&i-1-q[head]>=t)   head++;//如果区间长度大于t
        max_average=max(max_average,1.0*(a[i]-a[q[head]])/(i-q[head]+1));
    }
    cout<<max_average<<' '<<number<<endl;
    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;
}

大佬们看看我的判断方法有什么不对吗,我觉得和题解说的全部减去一个mid然后判断大于0的方法是等价的啊

2024/5/5 18:09
加载中...