C++实现从n根火柴中选取3根构成正三角形的方法计数

### 问题分析 要从`n`根火柴中选取 3 根构成正三角形，那么这 3 根火柴的长度必须相等。我们可以先读取所有火柴的长度，然后统计每种长度火柴的数量，对于每种长度的火柴，若其数量大于等于 3 根，则可以从中选取 3 根构成正三角形，根据组合数公式\(C_{m}^3=\frac{m!}{3!(m - 3)!}=\frac{m\times(m - 1)\times(m - 2)}{6}\)（其中\(m\)为该长度火柴的数量）来计算选取的方法数，最后将所有满足条件的长度的选取方法数相加即可。 ### 代码实现 ```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; // 计算从 m 个元素中选取 3 个元素的组合数 int combination(int m) { return m * (m - 1) * (m - 2) / 6; } int main() { int n; cin >> n; // 用于统计每种长度火柴的数量 unordered_map<int, int> lengthCount; // 读取每根火柴的长度并统计数量 for (int i = 0; i < n; ++i) { int length; cin >> length; lengthCount[length]++; } int totalWays = 0; // 遍历每种长度的火柴 for (const auto& pair : lengthCount) { int count = pair.second; // 如果该长度的火柴数量大于等于 3 根，则计算组合数并累加到总方法数中 if (count >= 3) { totalWays += combination(count); } } cout << totalWays << endl; return 0; } ``` ### 代码解释 1. **`combination`函数**：该函数用于计算从`m`个元素中选取 3 个元素的组合数，根据组合数公式\(\frac{m\times(m - 1)\times(m - 2)}{6}\)进行计算。 2. **`main`函数**： - 首先读取火柴的数量`n`。 - 然后使用`unordered_map<int, int>`来统计每种长度火柴的数量，遍历输入的每根火柴长度，将其数量加 1。 - 接着遍历`unordered_map`，对于每种长度的火柴，若其数量大于等于 3 根，则调用`combination`函数计算组合数并累加到`totalWays`中。 - 最后输出总方法数。 ### 复杂度分析 - **时间复杂度**：\(O(n)\)，其中\(n\)为火柴的数量。主要时间开销在于读取火柴长度和统计数量。 - **空间复杂度**：\(O(k)\)，其中\(k\)为不同长度火柴的种类数。主要空间开销在于存储每种长度火柴的数量。 ### 开发建议 - **输入验证**：在实际应用中，应添加对输入的验证，例如确保火柴数量`n`为正整数，火柴长度为非负整数等。 - **错误处理**：可以添加对输入异常情况的处理，例如输入格式错误、内存分配失败等。 - **性能优化**：如果火柴长度的范围较小，可以使用数组代替`unordered_map`来统计数量，以提高性能。 ### 相关学习资源 - C++ 官方文档：https://en.cppreference.com/w/ - 《C++ Primer》：经典的 C++ 学习书籍，涵盖了 C++ 的基础知识和高级特性。 ######[AI写代码神器 | 865点数解答 | 2026-03-01 17:19:18]