\(\text{WQS}\) 二分+斜率优化

若没有 \(k\) 的限制，可以用 \(f_i\) 表示剩 \(i\) 个人时获得的最大收益，那么当下一轮剩 \(j\) 个人时，这一轮就淘汰了 \(i-j\) 个人，获得 \(\dfrac{i-j}{i}\) 的奖金。

所以转移方程为 \(f_i=\max\{f_j+\dfrac{i-j}{i}\}(j<i)\)。

这个式子显然可以斜率优化，转化为 \(y=kx+b\) 的形式，即 \(\underline{\huge f_j}_y=\underline{\huge\dfrac{1}{i}}_k\times\underline{\huge j}_x+\underline{\huge f_i-1}_b\)。

现在考虑有 \(k\) 的限制，“恰好 \(k\) 个”显然是 \(\text{WQS}\) 二分的特征，其凸性读者可以自证。我只会打表找规律

另外，此题稍卡精度，所以我加了个时间限制。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const double eps=1e-20;
int n,K;
double f[N];
int q[N],cnt[N];
inline double Y(int i,int j){return f[i]-f[j];}
inline double X(int i,int j){return i-j;} 
inline double slope(int i,int j){return Y(i,j)/X(i,j);}
bool check(double k){
    int l=1,r=1;q[1]=0;
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++){
        while(l<r&&slope(q[l+1],q[l])>1.0/(double)i+eps)l++;
        int j=q[l];
        f[i]=f[j]+(double)(i-j)/(double)i-k;
        cnt[i]=cnt[j]+1;
        while(l<r&&slope(q[r],q[r-1])+eps<slope(i,q[r]))r--;
        q[++r]=i;
    }return cnt[n]>=K;
}
int main(){
    scanf("%d%d",&n,&K);
    double l=0,r=1e6;
    while(l+eps<r&&(double)clock()/CLOCKS_PER_SEC<=1.9){
        double mid=(l+r)/2.0;
        if(check(mid))l=mid;
        else r=mid;
    }printf("%.9lf\n",f[n]+l*K);
    return 0;
}