自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:09:21，当前版本为作者最后更新于2019-07-02 18:17:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本文同步发表于我的博客：https://www.alpha1022.me/articles/loj-3132.htm

发现踢人的顺序并不影响答案，所以我们不妨把每次踢的人都看成一段，并且倒序 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{aligned}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{aligned} $$

然后既然有了 $k$ 的限制，显然 WQS 二分直接上。

代码：

#include <cstdio>
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);
}