UVa 651 Deck

题目描述将若干张相同的矩形卡片沿桌边叠放每张卡片的短边与桌边平行且每张卡片最多与一张卡片接触即上下各一张形成一摞。通过小心摆放可以使整摞卡片伸出桌边的总长度最大。已知111张卡片最多伸出1/21/21/2张卡片长度。222张卡片最多伸出3/43/43/4张卡片长度。333张卡片最多伸出11/1211/1211/12张卡片长度。要求计算nnn张卡片n≤99999n \le 99999n≤99999能伸出的最大总长度以卡片长度为单位并四舍五入到小数点后333位。输入格式输入包含若干行每行一个非负整数nnnn≤99999n \le 99999n≤99999以文件结束符终止。输出格式首先输出一行标题# Cards Overhang注意#后有一个空格Cards和Overhang之间有两个空格。然后对于每个输入整数nnn输出一行格式为nnn右对齐占555列然后一个空格再输出悬伸长度小数点在列121212即总宽度为101010列右对齐保留三位小数。样例输入1 2 3 4 30输出1234567890123456 # Cards Overhang 1 0.500 2 0.750 3 0.917 4 1.042 30 1.997注第一行1234567890123456仅用于对齐指引不是输出的一部分。题目分析本题为经典的“卡片悬挑”问题。物理上为使悬挑总长度最大应从最上面一张卡片开始依次使每张卡片的重心恰好落在下方卡片的边缘上。设从上往下第kkk张卡片kkk从111开始相对于其下方卡片的最大悬伸长度为1/(2k)1/(2k)1/(2k)。因此nnn张卡片的总悬伸长度为overhang(n)∑k1n12k12∑k1n1k12Hn, \textit{overhang}(n) \sum_{k1}^{n} \frac{1}{2k} \frac{1}{2} \sum_{k1}^{n} \frac{1}{k} \frac{1}{2} H_n,overhang(n)k1∑n​2k1​21​k1∑n​k1​21​Hn​,其中HnH_nHn​为第nnn个调和数。由于nnn最大为999999999999999直接累加计算即可精度足够。解题思路预先计算数组overhang[0..99999]其中overhang[0] 0.0对于iii从111到999999999999999令overhang[i]overhang[i−1]12i. \textit{overhang}[i] \textit{overhang}[i-1] \frac{1}{2i}.overhang[i]overhang[i−1]2i1​.输出标题行。对每个输入的nnn按格式输出n和overhang[n]保留三位小数。由于查询次数不限预计算后每个查询为O(1)O(1)O(1)时间。复杂度分析预计算O(99999)O(99999)O(99999)次浮点加法时间常数。每个查询O(1)O(1)O(1)。空间复杂度O(100000)O(100000)O(100000)用于存储预计算结果。代码实现// Deck// UVa ID: 651// Verdict: Accepted// Submission Date: 2017-05-30// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);cout.setf(ios::fixed);cout.precision(3);cout# Cards Overhang\n;doubleoverhang[100000]{0.0};for(inti1;i99999;i)overhang[i]overhang[i-1]1.0/(double)(2*i);intcards;while(cincards){coutsetw(5)rightcards;coutsetw(10)rightoverhang[cards]\n;}return0;}总结本题利用物理模型的调和级数求和公式通过预计算避免了重复计算并以精确的格式输出。核心在于理解悬伸长度的累加规律以及正确处理浮点数输出格式。该解法简洁高效适用于大规模查询。