题目描述
你面临(n)名参赛者的挑战，最终要将他们全部战胜。
每一轮中，都会淘汰一些选手；你会得到这一轮奖金池中 被淘汰者 除以 这一轮对手总数 比例的奖金。
例如某一轮有(10)个对手，淘汰了(3)个，那么你将获得奖金池中(frac{3}{10})的奖金。
假设每一轮的奖金池均为一元，(Mirko)希望通过恰好(k)轮赢得比赛，那么他最多可能获得多少奖金呢？
你只需要输出答案保留(9)位小数即可。
题解
设(f_i)表示从后向前某一轮还剩了(i)个人的最大奖金
显然(f_i)可以由(f_j)转移((0 leq j < i))，状态转移方程(f_i = max(f_i, f_j + frac{i - j}{i}))。
假设对于决策(0 leq k < j < i)，(j)优于(k)
即(f_j + frac{i - j}{i} > f_k + frac{i - k}{i})
则(f_j - f_k > frac{j - k}{i})
可得(frac{f_j - f_k}{j - k} > frac{1}{i})
所以以此为判断依据，若队首下一个元素比队首优就让队首出队
同时每一次转移，记录一个(g_i)表示从后向前某一轮还剩了(i)个人时进行了几轮，(g[i] = g[q[l]] + 1)，返回(g[n] geq k)即可。
#include <iostream>
#include <cstdio>
#define double long double
using namespace std;
const int N = 1e5 + 5;
const double eps = 1e-12;
int n, k, q[N], g[N];
double ans, f[N];
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
return x * f;
}
double slope(int j, int k) {return (f[j] - f[k]) / (double)(j - k);}
int check(double mid)
{
int l, r;/**/ q[l = r = 1] = 0;
for(int i = 1; i <= n; i ++)
{
while(l < r && slope(q[l], q[l + 1]) - 1.0 / (double)i > eps) l ++;
f[i] = f[q[l]] + (double)(i - q[l]) / (double)i - mid; g[i] = g[q[l]] + 1;
while(l < r && slope(q[r - 1], q[r]) - slope(q[r - 1], i) < -eps) r --;
q[++ r] = i;
}
return g[n] >= k;
}
void work()
{
n = read(); k = read(); double l = 0, r = 1e6;
while(r - l >= -eps)
{
double mid = (l + r) / 2.0;
if(check(mid)) ans = mid, l = mid + eps;
else r = mid - eps;
}
check(ans); printf("%.9Lf
", f[n] + k * ans);//Lf
}
int main() {return work(), 0;}