发现踢人的顺序并不影响答案，所以我们不妨把每次踢的人都看成一段，并且倒序 DP。
这样的话，每一轮的总人数就比较好计算。
首先不考虑 \(k\)，设 \(f_i\) 表示从后往前数某一轮还剩 \(i\) 个人的最大奖金。
显然转移就枚举这一轮的下一轮还剩多少人，中间少的就是淘汰的。
有 \(f_i = \max\limits_{0 \le j < i}(f_j + \dfrac{i - j}i)\)。
假设对于决策 \(0 \le k < j < i\)，有 \(j\) 优于 \(k\)，即 \[\begin{align*} f_j + \dfrac{i - j}i & > f_k + \dfrac{i - k}i \\ f_j - f_k & > \dfrac{j - k}i \\ \dfrac{f_j - f_k}{j - k} & > \dfrac 1 i \end{align*}\]
然后既然有了 \(k\) 的限制，显然 WQS 二分直接上。
代码： 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
using namespace std;
const int N = 1e5;
const long double eps = 1e-12;
int n,k,g[N + 5];
int q[N + 5],head,tail;
long double f[N + 5];
long double l,r,mid;
inline long double slope(int x,int y)
{
return (f[x] - f[y]) / (x - y);
}
int check()
{
q[head = tail = 1] = 0;
for(register int i = 1;i <= n;++i)
{
for(;head < tail && slope(q[head],q[head + 1]) - 1.0 / i > eps;++head);
f[i] = f[q[head]] + (long double)(i - q[head]) / i - mid,g[i] = g[q[head]] + 1;
for(;head < tail && slope(q[tail - 1],q[tail]) - slope(q[tail],i) < -eps;--tail);
q[++tail] = i;
}
return g[n] >= k;
}
int main()
{
scanf("%d%d",&n,&k);
l = 0,r = 1e6;
for(register int i = 1;i <= 200;++i)
{
mid = (l + r) / 2;
if(check())
l = mid;
else
r = mid;
}
mid = l,check();
printf("%.9Lf\n",f[n] + k * mid);
}