题解 P5308 [COCI2019] Quiz
ADay
·
·
题解
更好的阅读体验
若没有 $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{f_j}_y=\underline{\dfrac{1}{i}}_k\times\underline{j}_x+\underline{f_i-1}_b$。
现在考虑有 $k$ 的限制，“恰好 $k$ 个”显然是 $\text{WQS}$ 二分的特征，其凸性读者可以自证。~~我只会打表找规律~~
另外，此题稍卡精度，所以我加了个时间限制。
Code
```cpp
#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;
}
```