题目描述 给定一组红色木棍和蓝色木棍： 红色木棍总共有 2N 根，给定一个长度为 N 的正整数序列 A，表示每个 A i ​ 的值对应 2 根长度为 A i ​ 的红色木棍。 蓝色木棍总共有 N 根，给定一个长度为 N 的正整数序列 B，表示每个 B i ​ 的值对应 1 根长度为 B i ​ 的蓝色木棍。 你需要使用这些木棍尽可能多地组成 等腰三角形，每个三角形必须使用： 两根 长度相等的红色木棍； 一根 蓝色木棍。 并且三角形必须满足三角形不等式，每根木棍只能使用一次。 请你计算最多能组成多少个等腰三角形。 输入格式 第一行：一个正整数 N，表示序列 A 和 B 的长度。（1≤N≤2×10 5 ） 第二行：N 个正整数 A 1 ​ ,A 2 ​ ,...,A N ​ （1≤A i ​ ≤10 6 ） 第三行：N 个正整数 B 1 ​ ,B 2 ​ ,...,B N ​ （1≤B i ​ ≤10 6 ） 输出格式 输出一个整数，表示最多能组成多少个满足要求的等腰三角形。c++代码

### 计算红色木棍和蓝色木棍最多能组成的等腰三角形数量 为了实现这一目标，我们需要考虑以下几个方面： 1. **定义等腰三角形条件** 等腰三角形是指至少有两条边长度相同的三角形。假设我们有一组红色木棍 `R` 和一组蓝色木棍 `B`，则可以通过枚举每种可能的组合来找到满足条件的等腰三角形。 2. **优化算法复杂度** 如果直接暴力枚举所有可能性，则时间复杂度过高。因此，我们可以先统计每种颜色木棍的频率表，再通过频率表快速查找符合条件的组合。 以下是完整的 C++ 实现代码： ```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; // 函数：计算最大等腰三角形数量 int countIsoscelesTriangles(const vector<int>& redSticks, const vector<int>& blueSticks) { unordered_map<int, int> freqRed, freqBlue; // 统计红色木棍的频率 for (auto stick : redSticks) { freqRed[stick]++; } // 统计蓝色木棍的频率 for (auto stick : blueSticks) { freqBlue[stick]++; } int totalTriangles = 0; // Case 1: 使用两根红色木棍作为相等边，一根蓝色木棍作为底边 for (const auto& pair : freqRed) { int length = pair.first; int count = pair.second; if (count >= 2) { // 至少需要两根相同长度的红色木棍 for (const auto& basePair : freqBlue) { int baseLength = basePair.first; if (baseLength < 2 * length && baseLength > abs(length - length)) { // 判断是否能构成三角形 totalTriangles += (count / 2) * basePair.second; // 每次取两根红色木棍配对 } } } } // Case 2: 使用两根蓝色木棍作为相等边，一根红色木棍作为底边 for (const auto& pair : freqBlue) { int length = pair.first; int count = pair.second; if (count >= 2) { // 至少需要两根相同长度的蓝色木棍 for (const auto& basePair : freqRed) { int baseLength = basePair.first; if (baseLength < 2 * length && baseLength > abs(length - length)) { // 判断是否能构成三角形 totalTriangles += (count / 2) * basePair.second; // 每次取两根蓝色木棍配对 } } } } return totalTriangles; } int main() { // 示例输入 vector<int> redSticks = {3, 3, 4}; vector<int> blueSticks = {3, 4, 4}; int result = countIsoscelesTriangles(redSticks, blueSticks); cout << "Maximum number of isosceles triangles: " << result << endl; return 0; } ``` #### 解释 - 我们使用哈希表 (`unordered_map`) 来存储每种颜色木棍的频率。 - 对于每一组可能的等腰三角形配置（红-红-蓝 或 蓝-蓝-红），检查是否存在有效的第三条边使得能够形成三角形[^1]。 - 时间复杂度主要由频率表构建决定，整体效率较高。 --- ###