[GCJKickstart2018RoundA] B. Lucky Dip

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://code.google.com/codejam/contest/9234486/dashboard#s=p1

有n个数，允许k次“取一个数再放回重新取”的操作，一个人希望拿到最大的那个数字。求取到数字最大的期望。

$k=0$时，期望就是均值，即$E_0=\frac{1}{n}\sum_{i=0}^nv_i$。

$k=1$时，每取到一个数可以有一次机会选择是否放回，但是期望拿到数字最大，因此要选取比$k=0$时期望大的数，$E_1=\frac{1}{n}\sum_{i=1}^n\mbox{max}(v_i,E_0)$。

可以推广：$E_k=\frac{1}{n}\sum_{i=1}^n\mbox{max}(v_i,E_{k-1})$。

假设计算$E_k$时，有$t$个数字使得$E_{k-1}$比$v_i$大，那么就有$n-t$个数使$E_{k-1}$比$v_i$小，他们的对$E_k$的贡献分别是$tE_{k-1}$和$\sum_{v<E_{k-1}}v$。我们可以对$v$排序，前者的$t$可以二分得到，后者可以维护一个前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 20020;
double v[maxn], sum[maxn];
int n, k;

int bs(int E) {
  int lo = 1, hi = n;
  int ret = -1;
  while(lo <= hi) {
    int mid = (lo + hi) >> 1;
    if(v[mid] <= E) {
      ret = mid;
      lo = mid + 1;
    }
    else {
      hi = mid - 1;
    }
  }
  return ret;
}

signed main() {
  freopen("in", "r", stdin);
  freopen("out", "w", stdout);
  int T, _ = 1;
  scanf("%d", &T);
  while(T--) {
    scanf("%d%d", &n, &k);
    memset(sum, 0, sizeof(sum));
    double E = .0;
    for(int i = 1; i <= n; i++) {
      scanf("%lf", &v[i]);
    }
    sort(v+1, v+n+1);
    for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + v[i];
    for(int i = 0; i <= k; i++) {
      int t = bs(E);
      E = (sum[n]-sum[t]) + t * E;
      E /= n;
    }
    printf("Case #%d: %.8f\n", _++, E);
  }
  return 0;
}