题解 P5308 【[COCI2019] Quiz】

Aleph1022 · 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，即

然后既然有了 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);
}