极差三元组计数

Problem Description

给定一个数组，请你计算有多少个三元组< i,j,k >满足0≤i,j,k

input

第一行输入一个正整数n。 第二行输入n个正整数aia_iai​。
3≤n≤200000,1≤a≤1093≤n≤200000,1≤a≤10^93≤n≤200000,1≤a≤109

ouput

一个整数，代表合法的三元组数量。

Sample Input 1

3
1 2 3

Sample Output 1

0

Sample Input 2

4
2 1 2 2

Sample Output 2

3

题目类型、难度、来源

• 类型：排序、暴力
• 难度：简单
• 来源：阿里春招-2023.3.15-第二题-极差三元组计数

总体思路：

• 此题要求三元组最大值和最小值相差1。也就是i,j,k里必须有两个相同，另一个不同，且两个数直接的差值必须是1。这就是一个组合数学的问题了。
• 可以先将数组从小到大排序。然后挨个遍历不同的元素，对于两个相差为1的数，假如较小的那个为a，较大的为b。a出现的次数是na，b出现的次数是nb。那就只有两种组合：aab，abb。
  • aab这种情况，需要从na个a里选出两个a（如果na大于1），从nb里选出一个b，即Cna2⋅Cnb1C_{na}^{2}·C_{nb}^{1}Cna2​⋅Cnb1​。
  • abb这种情况，需要从na个a里选出一个a，从nb里选出两个b（如果nb大于1），即Cna1⋅Cnb2C_{na}^{1}·C_{nb}^{2}Cna1​⋅Cnb2​。

AC代码

#include 
#include 
using namespace std;
int C_1(int t){return t;
}
int C_2(int t){return (t*(t-1))/2;
}
int main(){long long n;cin >> n;long long *a = new long long[n+5];for (long long i = 0; i < n; i++){cin >> a[i];}sort(a, a+n);long long *index = new long long[n+5];long long ni = 0, last_num = -1;for (int i = 0; i < n; i++){if (a[i] != last_num){index[ni++] = i;last_num = a[i];}}index[ni] = n;long long result = 0;for (long long i = 0; i < ni-1; i++){long long num = a[index[i]];long long next_num = a[index[i+1]];if (next_num-num != 1){continue;}long long count_num = index[i+1]-index[i];long long count_next_num = index[i+2]-index[i+1];if ((count_next_num + count_num < 3)||(count_num < 1)||(count_next_num < 1)){continue;}if (count_next_num > 1){result += C_1(count_num)*C_2(count_next_num);}if (count_num > 1){result += C_1(count_next_num)*C_2(count_num);}}cout << result;return 0;
}