题目描述

难度分:$1500$

输入$n(3 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

输出使$a[i] \times a[j] \times a[k]$最小且$i \lt j \lt k$的$(i,j,k)$三元组个数。

输入样例$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

算法

排序+分类讨论

虽然题目里说要求$i \lt j \lt k$，但是我们并不关心$(i,j,k)$里面谁是谁，所以随便找出来一个三元组，让下标最小的充当$i$，次小的充当$j$，最大的充当$k$即可。又因为数组$a$中的数都是正数，所以最小的三数之积就是最小的三个数乘积。

对数组$a$排序，然后一个哈希表$counter$统计每个元素值的频数，再利用双指针算法对有序数组$a$去重。分情况讨论：

1. 如果$a[1]$就已经不小于$3$个了，那最小积就是$a[1]^3$，从$counter[a[1]]$个$a[1]$中选$3$个出来就行，方案数为$C_{counter[a[1]]}^{3}$。
2. 如果$a[1]$和$a[2]$的频数不小于$3$个，假如$a[1]$只有一个，那选上这个$a[1]$，再从$counter[a[2]]$个$a[2]$中选$2$个$a[2]$，方案数为$C_{counter[a[2]]}^{2}$。假如$a[1]$有两个，那就选上这两个$a[1]$，再从$counter[a[2]]$个$a[2]$中选$1$个$a[2]$，方案数为$C_{counter[a[2]}^{1}$。
3. 最后就是$counter[a[1]]+counter[a[2]]+counter[a[3]] \geq 3$的情况，那就前两个数都选上（前两个数都只有一个），从$counter[a[3]]$个$a[3]$中再选$1$个$a[3]$即可，方案数为$counter[a[1]] \times counter[a[2]] \times counter[a[3]]$。

复杂度分析

时间复杂度

排序的时间复杂度为$O(nlog_2n)$，后面的分类讨论都是$O(1)$的，因此整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

排序的空间复杂度以快排为基准，为$O(log_2n)$。因此瓶颈在于开辟了一个哈希表存储数组$a$中元素值的频数，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <chrono>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, a[N];

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
  }
};

LL C3(int x) {
    return (LL)x*(x - 1)*(x - 2)/6;
}

LL C2(int x) {
    return (LL)x*(x - 1)/2;
}

int main() {
    scanf("%d", &n);
    unordered_map<int, int, custom_hash> counter;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        counter[a[i]]++;
    }
    sort(a + 1, a + n + 1);
    int cnt = unique(a + 1, a + n + 1) - a - 1;
    if(counter[a[1]] >= 3) {
        printf("%lld\n", C3(counter[a[1]]));
    }else if(counter[a[1]] + counter[a[2]] >= 3) {
        LL ans = 0;
        if(counter[a[1]] == 2) {
            ans += (LL)C2(counter[a[1]])*counter[a[2]];
        }else {
            ans += (LL)counter[a[1]]*C2(counter[a[2]]);
        }
        printf("%lld\n", ans);
    }else {
        printf("%lld\n", (LL)counter[a[1]]*counter[a[2]]*counter[a[3]]);
    }
    return 0;
}