题目大意
Codeforces 841C Leha and Function.
令\(F(n,k)\)为在集合\(\{x|x \in [1,n]\}\)中选择一个大小为k的子集，最小元素的期望值。
给定数组\(a_i,b_i\),满足\(\forall_{i,j}a_i \geqslant b_j\).求出\(a_i\)的一个排列\(a'_i\),使得\(\sum_{i} F(a_i,b_i)\)最大。
朱世杰恒等式
在这里介绍一个非常有用的关于组合数求和的公式——朱世杰恒等式(i.e. Hockey-stick identity):
\[
\sum_{i=m}^{n}\dbinom{i}{k} = \dbinom{n+1}{k+1} - \dbinom {m}{k+1}
\]
当\(m=k\)时:
\[
\sum_{i=m}^n \dbinom{i}{m} = \dbinom {n+1}{m+1}
\]
不失一般性，对于特殊情况作出证明，容易推广到第一个式子。
证明
对\(n\)施用数学归纳法。
当\(n=m\)时, 显然成立.
对于\(n-1 \geqslant m\), 假设对于\(n-1\)成立, 那么:
\(\sum_{i=m}^{n-1} \dbinom im = \dbinom {n}{m+1}\).
\(\sum_{i=m}^n \dbinom im = \dbinom{n}{m+1} + \dbinom {n}{m} = \dbinom {n+1}{m+1}\)
Q.E.D.
其他证明方法见维基百科
关于F(n,k)的推演
在比赛中, 我首先得到了\(F(n,k)\)的递推式:
\[F(n,k) = \frac kn F(n-1, k-1) + (1-\frac kn) F(n-1, k)\].
我们可以使用强数学归纳法证明:
\[F(n,k) = \frac {n+1}{k+1}\].
不过, 有一个更为简单的方法:
显然,
\[F(n,k) = \frac {1}{\dbinom{n}{k}}\sum_{i=1}^n i \dbinom{n-i}{k-1} \]
而:
\[\sum_{i=1}^n i\dbinom{n-i}{k-1} = \sum_{i=1}^{n-k+1}\sum_{j=1}^{n-k+1}\dbinom{n-j}{k-1}\\=\sum_{i=1}^{n-k+1}\sum_{j=k-1}^{n-i}\dbinom{j}{k-1} \\=\sum_{i=1}^{n-k+1} \dbinom{n-i+1}{k}\\=\sum_{i=k}^{n}\dbinom{i}{k} = \dbinom{n+1}{k+1}\]
于是:
\(F(n,k) = \frac{\dbinom{n+1}{k+1}}{\dbinom{n}{k}} = \frac {n+1}{k+1}\).
Q.E.D.
关于贪心的证明
那么问题就变成了:
给定数组\(a_i, b_i\),
\[\max \sum_{i=1}^n \frac{a_i+1}{b_i + 1}\].
我们证明, 给较大的\(a_i\)应搭配较小的\(b_i\).
对于\(0 \leqslant a_1 \leqslant a_2, 0 \leqslant b_1 \leqslant b_2\), 我们证明
\(a_1b_1 + a_2b_2 \leqslant a_1b_2 + a_2b_1\).
我们可以做差证明上面的式子.
那么我们可以使用证明贪心的常用方法,交换法(i.e. 冒泡排序法)来证明贪心的correctness.
算法
经过上面的推演,我们终于得到了这个问题的标算:
把b数组从小到大排序,a数组从大到小排序,一一对应即可.
然而,在比赛中,样例却直接给除了解法,令人遗憾.
比赛的时候推了很久，虽然早就知道贪心做法.