题解：扑克牌叠放悬垂问题（Deck）

题目分析

本题要求计算给定数量的扑克牌按规则叠放时，能伸出桌面边缘的最大长度。关键在于发现叠放规律与调和级数的关系，通过数学推导找到高效的计算方法。

问题推导

1. 物理原理：每张牌的重心需位于其下方支撑物（牌或桌面）的边缘上方。对于第 ( i ) 张牌（从顶部开始数，( i=1,2,\dots,n )），其最大悬垂长度为 ( \frac{1}{2i} ) 张牌长度。这是因为 ( i ) 张牌的总重心位置需恰好位于下方支撑物边缘，通过力矩平衡推导可得此结论。
2. 总悬垂长度：将每张牌的悬垂长度累加，得到总长度为前 ( n ) 项调和级数和的一半：
   [ \text{overhang} = \frac{1}{2} \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right) = \frac{1}{2} \sum_{i=1}^{n} \frac{1}{i} ]

算法思路

1. 预处理调和级数：预先计算前 ( 10^5 ) 项的调和级数前缀和，避免重复计算。这样每个查询的时间复杂度为 ( O(1) )。
2. 浮点精度处理：使用 round 函数对计算结果进行四舍五入，确保保留三位小数的准确性。
3. 格式化输出：按题目要求对齐输出牌数和结果，使用 C++ 的输入输出流控制符（如 setw、fixed、setprecision）实现精确格式化。

解决代码

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath> // 用于round函数
using namespace std;

int main() {
    const int MAX_N = 99999; // 最大牌数
    vector<double> harmonic(MAX_N + 1, 0.0); // 调和级数前缀和数组

    // 预处理调和级数前缀和
    for (int i = 1; i <= MAX_N; ++i) {
        harmonic[i] = harmonic[i - 1] + 1.0 / i;
    }

    cout << "Cards  Overhang" << endl; // 输出标题

    int n;
    while (cin >> n) { // 处理多个输入
        if (n == 0) { // 特殊情况：0张牌
            cout << right << setw(5) << n << "     " << fixed << setprecision(3) << 0.0 << endl;
        } else {
            double overhang = harmonic[n] / 2.0; // 计算总悬垂长度
            // 四舍五入到三位小数，避免浮点误差
            overhang = round(overhang * 1000) / 1000;
            // 格式化输出：牌数右对齐5列，结果左对齐，小数点后三位
            cout << right << setw(5) << n << "     " << fixed << setprecision(3) << overhang << endl;
        }
    }

    return 0;
}

代码解释

1. 预处理调和级数：

   • 使用 vector<double> harmonic 存储调和级数的前缀和，下标 i 表示前 i 项的和。
   • 通过循环计算每项的累加和，时间复杂度为 ( O(n) )，预处理完成后可快速查询任意 ( n ) 的调和和。

2. 输入处理与计算：

   • 读取输入的牌数 n，若 n=0，直接输出 0.000。
   • 否则，根据调和级数前缀和计算总悬垂长度，并通过 round 函数处理精度，确保结果四舍五入到三位小数。

3. 格式化输出：

   • right 和 setw(5) 确保牌数右对齐至第5列。
   • fixed 和 setprecision(3) 固定输出格式，使小数点后保留三位，且整体对齐到第12列。

复杂度分析

• 预处理时间复杂度：( O(MAX_N) )，其中 ( MAX_N = 99999 )，预处理一次即可应对所有查询。
• 单次查询时间复杂度：( O(1) )，直接通过数组查询和简单计算完成。
• 空间复杂度：( O(MAX_N) )，用于存储调和级数前缀和数组，占用空间约 400KB（每个 double 占8字节），完全满足内存限制。

该方法高效且准确，能够快速处理题目给定范围内的所有输入，确保在时间和空间上均达到最优。