首页 > 其他 > 详细

CodeForces 939E Maximize!

时间:2018-02-20 14:15:33      阅读:121      评论:0      收藏:0      [点我收藏+]

标签:1.0   ems   get   scan   tmp   oid   bit   如果   long long   

 

题目链接

 

我的做法是离线进行分治。

假设选择第$i$个数字作为最大值,那么比它小的部分的数字肯定是某个前缀,也就是要去寻找选择哪个前缀使得平均值最小。

可以发现前缀的寻找具有决策单调性,也就是说,如果选择第$i$个数字作为最大值的时候,前缀是选择了$[1, p]$;那么选择第$i$个数字之后的数字作为最大值的时候,前缀是选择肯定大于等于$p$位置。因此分治就可以了。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
long long sum[maxn];
long long a[maxn];
double mean[maxn];
double ans[maxn];
int n;
queue<int> q;

void dp(int l, int r, int dl, int dr) {
  int mid = (l + r) >> 1, dm = dl;
  double g = 2e9;
  for(int i = dl; i <= dr && i < mid; i ++) {
    double tmp = 1.0 * (sum[i] + a[mid]) / (i + 1);
    if(tmp < g) g = tmp, dm = i;
  }
  ans[mid] = g;
  if(l < mid) dp(l, mid - 1, dl, dm);
  if(r > mid) dp(mid + 1, r, dm, dr);
}

int main() {
  int Q;
  scanf("%d", &Q);
  while(Q --) {
    int op;
    scanf("%d", &op);
    if(op == 1) {
      long long x;
      scanf("%lld", &x);
      n ++;
      a[n] = x;
      sum[n] = sum[n - 1] + a[n];
    } else {
      q.push(n);
    }
  }
  dp(1, n, 1, n);
  for(int i = 1; i <= n; i ++) {
    ans[i] = 1.0 * a[i] - ans[i];
  }
  ans[1] = 0.0;
  for(int i = 2; i <= n; i ++) {
    ans[i] = max(ans[i], ans[i - 1]);
  }
  while(!q.empty()) {
    printf("%.8f\n", ans[q.front()]);
    q.pop();
  }
  return 0;
}

 

CodeForces 939E Maximize!

标签:1.0   ems   get   scan   tmp   oid   bit   如果   long long   

原文:https://www.cnblogs.com/zufezzt/p/8455152.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号