1、环境配置：

• 系统：win10
• 编程语言：C
• 编译器：DevC++

2、算法思想：

1、先把三个数组A，B，C从小到大排序
2、以中间的数组B[i]为主线，找A中比B[i]小的有q个，找C中比B[i]大的有m个，则B[i]对应的递增三元组有q*m个。这样依次把所有B[i]对应的递增三元组求出来，加一起就能得到最终结果。

3、代码：

/*
《求递增三元组》
*/

#include <stdio.h>
#include <stdlib.h>

int make_rand();//产生随机数函数
void init_func(int a[],int n);//数组初始化函数 
int MergeSort(int sourceArr[], int tempArr[], int low, int high);//归并排序 


int main() {
    long long answer = 0;
    int A[3]={1,1,1};
    int B[3]={2,2,2};
    int C[3]={3,3,3};
    int A_1[3];
    int B_1[3];
    int C_1[3];
//  init_func(A,3);
//  init_func(B,3);
//  init_func(C,3);
    for(int s=0;s<3;s++){
        printf("%d,",A[s]);
    } 
    printf("\n");
    for(int s=0;s<3;s++){
        printf("%d,",B[s]);
    } 
    printf("\n");
    for(int s=0;s<3;s++){
        printf("%d,",C[s]);
    } 
    printf("\n");
    MergeSort(A,A_1,0,2);
    MergeSort(B,B_1,0,2);
    MergeSort(C,C_1,0,2);
    
    int p=0;
    int q=0;
    for(int i=0;i<3;i++){
        while((p<3)&&(A[p]<B[i])){
            p++;
        }
        while((q<3)&&(C[q]<=B[i])){
            q++;
        }
        answer += p*(3-q);
    }
    printf("%d",answer);   
}

//产生随机数函数
int make_rand()
{
    int a;
    a = rand();
    return a%1000;
} 

//数组初始化
void init_func(int a[],int n)
{
    for(int i=0;i<n;i++)
    {
        a[i]=make_rand();
    }
} 

//归并排序 
int MergeSort(int sourceArr[], int tempArr[], int low, int high)
{
    int mid;
    if(low < high)
        {
            mid = (low + high) / 2;
            MergeSort(sourceArr, tempArr, low, mid);//左边归并 
            MergeSort(sourceArr, tempArr, mid + 1, high);//右边归并 
            int i = low, j = mid + 1, k = low;//借用第三个数组，左右合并。 
            while(i <= mid && j <= high)
            {
                if(sourceArr[i] < sourceArr[j])
                {
                    tempArr[k] = sourceArr[i];
                    k=k+1;
                    i=i+1;
                }   
                else
                {
                    tempArr[k] = sourceArr[j];
                    k=k+1;
                    j=j+1;
                }
                        
            }   
            while(i <= mid)
            {
                tempArr[k] = sourceArr[i];
                k=k+1;
                i=i+1;
            }
                
            while(j <= high)
            {
                tempArr[k] = sourceArr[j];
                k=k+1;
                j=j+1;
            }
            //最后再把tempArr中的值给sourceArr赋值填回去。 
            for (int p = low; p <= high; p++)
                sourceArr[p] = tempArr[p];
        }
    return 0;
}
    

4、结果展示：

验证.png

5、反思总结：

• 伪代码如下：

Merge_Sort(a[1...n]);//该函数是归并排序函数，会把a数组中元素从小到大排序。
int find_number(int A[1...n],int B[1...n],int C[1...n])
{
    //先将三个数组归并排序,这里用其他排序方法也行，只要保证从小到大就好 
    Merge_Sort(A[1...n]);
    Merge_Sort(B[1...n]);
    Merge_Sort(C[1...n]);
    
    //然后求解递增三元组的个数
    long int answer;
    int p=0;
    int q=0;
    for i=0 to i=n do{
        while((p<3)&&(A[p]<B[i])) do p++;//找到A中小于B[i]的数记作p 
        while((q<3)&&(C[q]<=B[i])) do q++;//找到C中小于等于B[i]的数记作q
        answer += p*(n-q);
    } 
    return answer; 
}