有没有大佬帮忙看一下怎么优化

2024-07-16 13:12:31

发布于：广东

13阅读

0回复

0点赞

A24633.独特三元组

#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,a[1000001]; cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(a[i]<a[j]&&a[i]<a[k]&&a[j]<a[k]) cnt++;
}
}
}
cout<<cnt;
return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 3

小ZUZ

其实不用这么麻烦

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    unordered_map<int, int> count;
    for (int i = 0; i < N; ++i) {
        count[A[i]]++;
    }
    long long total_triples = 0;
    long long total_singles = 0;
    long long total_pairs = 0;
    for (const auto& pair : count) {
        total_triples += total_pairs * pair.second;
        total_pairs += total_singles * pair.second;
        total_singles += pair.second;
    }
    cout << total_triples << endl;
    return 0;
}

2024-07-16 来自广东

6
回复小ZUZ
解释一下呗

2024-07-17 来自广东
0
小ZUZ
回复6
假设有
𝑁
N 个元素，且每个元素各不相同，那么满足题目要求的三元组数量就是这
𝑁
N 个元素中任意取
3
3 个元素的组合。也就是
(
𝑛
3
)

𝑛
×
(
𝑛
−
1
)
×
(
𝑛
−
2
)
/
1
(
3
n

)=n×(n−1)×(n−2)/1。

如果有重复的元素呢？我们只需要把重复的元素再“去除”掉就行。

2024-07-17 来自广东
0
小ZUZ
回复小ZUZ
tim老师没跟你讲吗

2024-07-17 来自广东
0

复仇者_帅童
自己想
提示：可以把总共的组合数减去至少两个相同的组合数

2024-07-16 来自广东
0
小ZUZ
e

2024-07-16 来自广东
0

全部评论 3

假设有 𝑁 N 个元素，且每个元素各不相同，那么满足题目要求的三元组数量就是这 𝑁 N 个元素中任意取 3 3 个元素的组合。也就是 ( 𝑛 3 )

热门讨论

假设有
𝑁
N 个元素，且每个元素各不相同，那么满足题目要求的三元组数量就是这
𝑁
N 个元素中任意取
3
3 个元素的组合。也就是
(
𝑛
3
)