3 solutions
-
0
难以言喻的一题,再一次感觉到了我的愚蠢
#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