AcWing5277. 三元组

给定一个长度为 n 的正整数数组 a1,a2,…,an

请你计算，一共有多少个三元组 (i,j,k)（1≤i<j<k≤n），使得 ai⋅aj⋅ak 为最小可能值。

输入格式

第一行包含整数 n。

第二行包含 n 个正整数 a1,a2,…,an。

输出格式

一个整数，表示满足条件的三元组的数量。

数据范围

前 3 个测试点满足，3≤n≤6。
所有测试点满足，3≤n≤105，1≤ai≤109。

输入样例1：

4
1 1 1 1

输出样例1：

4

输入样例2：

5
1 3 2 3 4

输出样例2：

2

输入样例3：

6
1 3 3 1 3 2

输出样例3：

1

代码实现 

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long 
const int N=1e5+10;int a[N];int C(int a,int b){int mid=1;for(int i=a,j=1;j<=b;i--,j++)mid=mid*i/j;return mid;
}signed main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);int x=1;while(x<=n&&a[x]==a[x+1])x++;         //统计第一小的数int y=x+1;while(y<=n&&a[y]==a[y+1])y++;         //统计第二小的数int z=y+1;while(z<=n&&a[z]==a[z+1])z++;         //统计第三小的数z-=y;y-=x;int ans;if(x>=3)ans=C(x,3);                   //如果第一小的数有3个或者以上，答案就为从第一小的数内选择3个进行组合else if(x+y>=3)ans=C(y,3-x);          //如果第一小的数不够3个，则第一小的数一定全部选，不同的情况就有从y中选剩下的来决定  else ans=C(z,1);                      //如果第一小和第二小都不够则再从第三小中选出来一个cout<<ans<<endl;return 0;
}