题目分析:
- 二分平均数,将原数列减去平均数,选 sum[i]−min(sum[j])是否大于等于0
- 注意答案要用 r来转 int
Code:
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define eps 1e-6
int n,L;
double a[maxn],b[maxn],s[maxn];
inline bool check_(double x) {
s[0]=0;
for(int i=1;i<=n;++i) {
b[i]=a[i]-x;
s[i]=s[i-1]+b[i];
}
double mind=3000,maxd=-3000;
for(int i=L;i<=n;++i) {
mind=min(mind,s[i-L]);
maxd=max(maxd,s[i]-mind);
if(maxd>=0) return true;
}
if(maxd>=0) return true;
else return false;
}
void readda_() {
scanf("%d%d",&n,&L);
double r=-1;
for(int i=1;i<=n;++i) {
scanf("%lf",&a[i]);
r=max(r,a[i]);
}
double l=0,mid;
while(r-l>eps) {
mid=(l+r)/2;
if(check_(mid)) {
l=mid;
}
else r=mid;
}
printf("%d",(int)(r*1000));
}
int main() {
freopen("a.txt","r",stdin);
readda_();
return 0;
}