本文主要是介绍B. Forming Triangles，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
map
可以理解成一个简单的数组，只是下标可以变成Key,也就是所谓的索引
通过向 map 中插入一个类型为 pair<Key, T> 的值可以达到插入元素的目的，例如
mp.insert(pair<string,int>("Alan",100));
erase(key) 函数会删除键为 key 的 所有 元素。返回值为删除元素的数量。
erase(pos): 删除迭代器为 pos 的元素，要求迭代器必须合法。
erase(first,last): 删除迭代器在 [first,last) 范围内的所有元素。
clear() 函数会清空整个容器。
一般情况下推荐使用 find() 函数来寻找特定键的元素。
#include<bits/stdc++.h>using namespace std;int main()
{int t;cin>>t;while(t--){int n;cin>>n;map<int,int> mp;for(int i=1;i<=n;i++){int x;cin>>x;++mp[x];}long long res=0;int sum=0;for(auto it:mp){long long cnt=it.second;if(cnt>=3)res+=cnt*(cnt-1)*(cnt-2)/6;if(cnt>=2)res+=cnt*(cnt-1)/2*sum;sum+=cnt;}cout<<res<<endl;}return 0;
}
注意该题n的数据范围是3e5
也就是说遍历三层循环求解妥妥超时
刚开始还以为是什么神奇的算法
结果发现是2的次方的问题，假设一条边严格大于另一条边，长度至少是另一条边的两倍，假设有三条边，a,b,c，长度依次递减，并且是严格递减，那么a至少是b的两倍，b至少是c的两倍，那么b+c一定严格小于a，难以构成三角形
假设b不严格大于c，假设b=c,a严格大于b，那么还是不满足要求，因为取一个极端情况，a刚好是 b的两倍，那么b+c=a
所以只有可能出现 a=b>=c，可以使得三条边可以构成三角形
假设三条边都相等，可以使用组合数来求解答案
从所有相等的边里面选3条边可以构成一个三角形，假设该长度的出现次数是7，那么答案就是， C 7 3 C ^3_7 C73,(把数学公式打出来还挺难的，还得学，做题挺难的，还得练)
假设有两条边相等，也就是一个等腰三角形，那么底一定要严格小于腰（不严格小于就是等边三角形，上面已经考虑过了）
假设腰的长度的出现次数等于7， C 7 2 C^2_7 C72表示选择两个相等的腰，然后再乘以严格小于腰的长度的边出现的次数即可
严格小于腰的长度的边的出现的次数用sum来进行保存
因为是从小到大遍历的map里面的元素，所以保证了严格小于
用map的索引表示边的长度，map的第二个变量表示的是该长度的边出现的次数
最后输出答案即可
这篇关于B. Forming Triangles的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
