B. Makes And The Product

原题地址

原题地址：http://codeforces.com/contest/817/problem/B?csrf_token=0c0d6f2e840e29e82ee292038434d486

解题思想

/*
方法一：
第一步：从小到大排序
第二步：找出数组中与a[2]相同的个数cot
第三步：分类讨论
if(a[2] == a[0])
说明最小的前三个值相同。所以就变成了排列组合问题，
A(cnt,3)/A（3,3）
else if(a[2] == a[1])
求A(cnt,2)/A(2,2)
else
 cnt的个数

显然此方法不具有通用性，只对这个题还是比较好的。
方法二：也就是官方的题解，说是求前缀数组与后缀数组，然后。。。
英文的，还没搞懂。懂了在更新


*/

代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int a[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; ++i)
        scanf("%d", &a[i]);
    sort(a,a+n);
    ll cnt = 0; //这里一定要为ll类型，否则溢出
    for(int i=0; i<n; ++i)
        if(a[i] == a[2])
           cnt++;
    if(a[2] == a[0])
        printf("%lld",cnt*(cnt-1)*(cnt-2)/6);
    else if(a[2] == a[1])
        printf("%lld", cnt*(cnt-1)/2);
    else
        printf("%lld", cnt);
    return 0;
}