实数折磨人啊啊啊啊啊啊啊
好,实数应该是最反人类的东西了......
这个害得我调了0.5天才过。
大意是这样的:给你一个数列,求其中不少于f个的连续数的最大平均值。
不禁想起寒假的课程来...
此处应该二分ans,每次把数列减去ans后判断是否有不少于f的一段sum>=0
大喜过望,写了个二分,然后发现不会O(1)判断...
冥思苦想无果之后不由得去看题解。发现要维护前缀和和1~i-f+1的最小前缀和即可。
然后就被实数卡了一天。。。
最后发现还是写的朴素点好。要相信出题人头脑简单不会拿一大堆if来写二分。
AC代码:
1 #include2 #include 3 using namespace std; 4 const int INF = 0x7f7f7f7f, N = 100010; 5 const double eps = 1e-5; 6 int f[N], n, F; 7 double a[N]; 8 bool check(double k) { 9 for(int i=1;i<=n;i++) {10 a[i] = f[i] - k;11 a[i] += a[i-1];12 }13 double small = 0, sum=0; // small != INF, small = 014 for(int i = F; i <= n; i++) {15 sum = a[i] - small;16 if(sum >= 0) {17 return true;18 }19 small = min(small, a[i-F+1]);20 }21 return false;22 }23 24 int main() {25 //freopen("in.in","r",stdin);26 //freopen("my.out","w",stdout);27 scanf("%d%d",&n,&F);28 int large = -INF, small = INF;29 for(int i=1;i<=n;i++) {30 scanf("%d",&f[i]);31 large = max(large, f[i]);32 small = min(small, f[i]);33 }34 double l = small, r = large, mid;35 while(r-l>eps) {36 //printf("%.10lf %.10lf \n",l,r);37 mid = (l + r) / 2;38 if(check(mid)) {39 l = mid;40 }41 else {42 r = mid;43 }44 }45 46 printf("%d",(int)(r*1000));47 return 0;48 }