自动搬运

查看原文

来自洛谷，原作者为

	p878567 以下证明：这一算法的时空复杂度是 $o(+\infty)$

搬运于2025-08-24 21:32:38，当前版本为作者最后更新于2018-10-01 14:25:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

话说这么多人怎么只找规律却不证明？ 加热方法很简单，加热第一杯，并依次传递到每一杯，然后加热第二杯并依次传递，直到加热最后一杯。这其实是个贪心，证明从略。

下面解决怎么算的问题。

方法一：时间$O(n^2)$,空间$O(n^2)$

令$f[i][j]$表示第$i$杯水加热并传给第$j$杯后，第$j$杯的热量，（$f[i][i]=\frac{420000}{n}$，否则后面的递推式不能用）答案为$\displaystyle\sum_{i=1}^{n}(f[i-1][i]+f[i][i])$。

由定义可知：

$f[i][j]=\begin{cases}\frac{420000}{n}&\quad(i=j)\\0&\quad(i=0)\\\frac{f[i-1][j]+f[i][j-1]}{2}&\quad\text{其它情况} \end{cases}$

第三种情况是因为： $f[i][j]=f[i-1][j]+\frac{f[i][j-1]-f[i-1][j]}{2}=\frac{f[i-1][j]+f[i][j-1]}{2}$

计算递推式即可。

方法二：时间$O(n)$,空间$O(1)$

由前面的分析，我们有：

$f[i-1][i]=\frac{f[i-1][i-1]}{2}+\frac{f[i-2][i]}{2}=\frac{f[i-1][i-1]}{2}+\frac{f[i-2][i-1]}{4}+\frac{f[i-3][i]}{4}$

$\quad=\frac{f[i-1][i-1]}{2}+\frac{f[i-2][i-2]}{8}+\frac{2(f[i-3][i-1])}{8}+\frac{f[i-4][i]}{8}$

$\quad=\dots$

$\quad=\frac{k_1\cdot f[i-1][i-1]}{2}+\frac{k_2\cdot f[i-2][j-2]}{8}+\dots+\frac{k_j\cdot f[i-j][i-j]}{2^{2j-1}}+\dots+\frac{k_{n-1}\cdot f[1][1]}{2^{2n-3}}$

$\quad=\displaystyle\sum^{i-1}_{j=1}(\frac{k_j}{2^{2j-1}}\cdot \frac{420000}{n})$

由数学归纳法，我们得到$k_i$在意义上为：

边长为n的方阵中，除起点和终点外，其余各点都在左上——右下的对角线以下的一半（不含对角线上）的，从$(n,n)$到$(n-i,n-i)$的且只往上或右走的路径的数量，即：

$k_i=C_{i-1}\text{（这里的C是卡特兰数！）}$

卡特兰数？自己查！

于是：

$f[i-1][i]=\displaystyle\sum^{i-1}_{j=1}(\frac{C_{j-1}}{2^{2j-1}}\cdot \frac{420000}{n})$

$\quad=\displaystyle\sum^{i-1}_{j=1}(\frac{\frac{\binom{j-1}{2(j-1)}}{j}}{2^{2j-1}}\cdot \frac{420000}{n})$

$\quad=\displaystyle\sum^{i-1}_{j=1}(\frac{[2(j-1)]!}{2^{2j-1}\cdot j!\cdot (j-1)!}\cdot \frac{420000}{n})$

$\therefore f[i][i+1]-f[i-1][i]=\frac{(2i-2)!}{2^{2i-1}\cdot i!\cdot (i-1)!}\cdot \frac{420000}{n}$

令上式为$g[i]$，则：

$\frac{g[i+1]}{g[i]}=\frac{\frac{(2i)!}{2^{2i+1}\cdot (i+1)!\cdot i!}}{\frac{(2i-2)!}{2^{2i-1}\cdot i!\cdot (i-1)!}}=\frac{2^{2i-1}(2i)!i!(i-1)!}{2^{2i+1}(2i-2)!(i+1)!i!}=\frac{2i-1}{2i+2}$

而$g[1]=\frac{210000}{n}$， 于是可依次求出$g$的值，从而求出$420000-\displaystyle\sum^{n}_{i=1}f[i-1][i]$的值，此值即为答案。

做省选题的人不至于还要代码吧

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	double ans = 0, f = 420000.00/n, g = 210000.00/n;
	for (int i = 1; i <= n; i++) {
    	ans += f;
		f += g;
		g = g*(2*i-1)/(2*i+2);
	}
	cout << fixed << setprecision(2) << 420000 - ans << endl;
}