题目描述

你面临\(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\n", f[n] + k * ans);//Lf
}
int main() {return work(), 0;}