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位。

输入格式

输入包含若干行，每行一个非负整数nnn（n≤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)=∑k=1n12k=12∑k=1n1k=12Hn, \textit{overhang}(n) = \sum_{k=1}^{n} \frac{1}{2k} = \frac{1}{2} \sum_{k=1}^{n} \frac{1}{k} = \frac{1}{2} H_n,overhang(n)=k=1∑n2k1=21k=1∑nk1=21Hn,

其中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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;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(inti=1;i<=99999;i++)overhang[i]=overhang[i-1]+1.0/(double)(2*i);intcards;while(cin>>cards){cout<<setw(5)<<right<<cards;cout<<setw(10)<<right<<overhang[cards]<<'\n';}return0;}