题目描述
你正在参加盛大的Kickstart幸运角活动，其中包含许多诱人的奖品（还有一些不太好的奖品）！
在这个活动中，有一个包含N个物品的包。
包中的第i个物品的价值为$V_i$。
你需要手伸进袋子里随意抽出一件物品; 包中的所有物品都有相同的被选择概率。
在你抽出一件物品之后，你可以保留它，或者将它放回包中再抽一次。 （请注意，被放回的物品和包内的其他物品在接下来的抽取中被抽中的概率相同。）
你最多只能重抽K次， 如果你连续重抽了K次，那么你将不得不保留被你第K+1次抽出的物品。
如果你以最佳方式进行游戏从而使得游戏结束后得到的物品的价值尽可能大，则得到物品价值的期望值是多少？
输入格式
第一行包含整数T，表示共有T组测试数据。
每组数据占两行，第一行包含两个整数N和K，分别表示物品个数和重抽最大次数。
第二行包含N个整数，其中第i个数为第i个物品的价值$V_i$。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为“Case #x: y”，其中x为组别编号（从1开始），y为物品价值的期望值。
y在正确答案的10−6的绝对或相对误差范围内，则视为正确。
数据范围
$1 \leq T \leq 100$
$ 1 \leq V_i \leq 10_{}^{9}$
$ 1 \leq N \leq 20000 $
$ 1 \leq K \leq 50000 $
样例
输入样例
5
4 0
1 2 3 4
3 1
1 10 1
3 15
80000 80000 80000
1 1
10
5 3
16 11 7 4 1
输出样例
Case #1: 2.500000
Case #2: 6.000000
Case #3: 80000.000000
Case #4: 10.000000
Case #5: 12.358400
算法1
(贪心 + 二分) $O((N + K)logN)$
我们考虑一下两个方面：
- 1.当我们一次不能重抽时，所得到到的期望值即为平均值
- 2.当我们重抽多次时，可以这样考虑：
- 当我们重抽的价值比上一轮的期望值小，我们就选择逆天改命，再抽一次，而再抽一次的后果就是仍维持上一轮的期望值，
- 如果我们重抽的价值比上一轮的期望值大，则选择不再重抽，保留该物品。
我们如果单纯以这样方式寻找正常有$O(n^2)$的时间复杂度做法，这个做法在KickStart是可以过的，但是在Acwing是不能过的，所以我们要考虑优化：
- 首先我们想到的就是在每次循环下，在价值数组找到区分上一次期望值的分界点，想到最直接的做法就是二分。
- 因此我们还要先将数组进行排序，然后还有先生成一个后缀和数组便于最后求解。
时间复杂度
快速排序时间复杂度O(NlogN),
循环K次
二分复杂度O(logN),
总的时间复杂度O((N + K)logN)。
参考文献
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 20010;
const int M = 50010;
int T;
int n, k;
int a[N];
LL s[N];
double dp[M];//保留每一轮期望值
int main()
{
cin >> T;
int cnt = 1;
while(T--){
memset(s, 0, sizeof s);
double sum = 0;
double av;
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i], sum += a[i];
av = sum * 1.0 / n;
sort(a, a + n);
for(int i = n - 1; i >= 0; i --) s[i] = s[i + 1] + a[i];
dp[0] = av;
for(int j = 1; j <= k; j ++){
int l = 0, r = n - 1;
while(l < r){
int mid = l + r >> 1;
if(a[mid] >= dp[j - 1]) r = mid;
else l = mid + 1;
}
//int l = upper_bound(a, a + n, dp[j-1]) - a;
dp[j] = (double)(dp[j - 1] * l + s[l]) / n;
}
printf("Case #%d: %.6lf\n", cnt ++, dp[k]);
}
return 0;
}
