2025-10-27 16:31:49
发布于：广东
5阅读
0回复
0点赞
tainanle
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n); // 使用long long避免乘法溢出
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end()); // 排序数组，便于后续处理
// 情况1：i < j，a[i] == a[j]，寻找k > j且a[k] < 2*a[i]
int case1 = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (a[i] == a[j]) {
long long target = 2 * a[i]; // 两边之和
// 查找[j+1, n)范围内第一个 >= target的位置
auto it = lower_bound(a.begin() + j + 1, a.end(), target);
int count = it - (a.begin() + j + 1); // 符合条件的k的数量
case1 += count;
}
}
}
// 情况2：j < k，a[j] == a[k]，i < j（i的数量为j个）
int case2 = 0;
for (int j = 0; j < n; ++j) {
for (int k = j + 1; k < n; ++k) {
if (a[j] == a[k]) {
case2 += j; // i可以是0到j-1，共j个
}
}
}
// 计算等边三角形数量（去重）
unordered_map<long long, int> freq;
for (long long num : a) {
freq[num]++;
}
int equilateral = 0;
for (auto& pair : freq) {
int c = pair.second;
if (c >= 3) {
// 组合数C(c,3) = c*(c-1)*(c-2)/6
equilateral += c * (c - 1) * (c - 2) / 6;
}
}
// 总数量 = 情况1 + 情况2 - 重复计算的等边三角形
int total = case1 + case2 - equilateral;
cout << total << endl;
return 0;
}
这里空空如也
有帮助，赞一个