3 solutions

  • 0
    @ 2022-6-6 21:43:04

    难以言喻的一题,再一次感觉到了我的愚蠢

    #include<iostream>
    using namespace std;
    #define MAX 100007
    #define INF 0x3f3f3f3f
    
    double l=1e5+7,r=0;
    int n,f;
    int a[MAX],s[MAX];
    
    bool check(double ave){
    	double sum1=s[f-1]-ave*(f-1);
    	for(int i=f;i<=n;i++){
    		double sum2=s[i]-s[i-f]-ave*f;
    		sum1=sum1+a[i]-ave;
    		sum1=max(sum1,sum2);
    		if(sum1>-1e-5)return false;
    	}
    	return true;
    }
    
    double search(double L,double R){
    	double mid;
    	while(R-L>=1e-5){
    		mid=(L+R)/2;
    		if(check(mid))R=mid;
    		else L=mid;
    	}
    	return R;
    }
    
    int main(){
    	ios::sync_with_stdio(false);
    	cin>>n>>f;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		if(a[i]>r)r=a[i];
    		if(a[i]<l)l=a[i];
    		s[i]=s[i-1]+a[i]; 
    	}
    	
    	double ans=search(l,r);
    	cout<<(int)(ans*1000);
    	return 0;
    }
    

    Information

    ID
    167
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    42
    Accepted
    12
    Uploaded By