从 n 根火柴中取 3 根构成正三角形的取法数量计算方法

### 思路分析 要从 `n` 根火柴里选 3 根组成正三角形，关键在于找出长度相同且数量不少于 3 的火柴。可以先统计每种长度火柴的出现次数，再依据组合数公式计算每种长度能构成正三角形的组合数，最后将所有符合条件的组合数相加。 ### Python 代码实现 ```python # 读取火柴数量 n = int(input()) # 读取每根火柴的长度 lengths = list(map(int, input().split())) # 用于统计每种长度火柴的数量 length_count = {} for length in lengths: if length in length_count: length_count[length] += 1 else: length_count[length] = 1 # 初始化方案数量 total_ways = 0 # 遍历每种长度及其对应的数量 for count in length_count.values(): if count >= 3: # 计算组合数 C(count, 3) total_ways += count * (count - 1) * (count - 2) // 6 # 输出组成方案的数量 print(total_ways) ``` ### C++ 代码实现 ```cpp #include <iostream> #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; if (count >= 3) { totalWays += combination(count); } } cout << totalWays << endl; return 0; } ``` ### 复杂度分析 - **时间复杂度**：$O(n)$，这里的 $n$ 是火柴的数量。主要时间消耗在统计每种长度火柴的数量上。 - **空间复杂度**：$O(k)$，$k$ 是不同长度火柴的种类数，主要用于存储每种长度火柴的数量。 ######[AI问答 | 602点数解答 | 2026-03-01 17:35:57]