递增三元组

难度：简单3星

题目描述：

给定三个整数数组

A = [A1, A2, ... AN],

B = [B1, B2, ... BN],

C = [C1, C2, ... CN]，

请你统计有多少个三元组(i, j, k) 满足：

一：1 <= i, j, k <= N

二：Ai < Bj < Ck

【输入格式】

第一行包含一个整数N。

第二行包含N个整数A1, A2, ... AN。

第三行包含N个整数B1, B2, ... BN。

第四行包含N个整数C1, C2, ... CN。

对于30%的数据，1 <= N <= 100

对于60%的数据，1 <= N <= 1000

对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

【输出格式】

一个整数表示答案

【样例输入】

3

1 1 1

2 2 2

3 3 3

【样例输出】

27

资源约定：

峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 1000ms

-------------------------------思路和分析----------------------------------

我们先对A，B，C排序。

对于B中的元素B[j]，进行如下操作：

1.对于A，我们找到两个下标i。有A[i]

这样我们就找到A中所有<B[j]的个数，即为(i+1)个。

2.同样我们在C中找的下标k。有C[k]>B[j]&&C[k-1]<=B[j].

这样我们就找到C中所有>B[j]的个数，即为(N-k)个。

那么我们就找到了，所有对于B[j]满座条件的个数count=(i+1)*(N-k)个

那么所有的可能即为对于B中每个元素个数之和。

 ********************复杂度分析*******************************

首先快速排序O(3*nlogn)+遍历B找到i,k为O(N*(i+k))

                                            所以复杂度为O(n**2)

--------------------！！！！！！特殊情况分析！！-------------------

即为对找不到我们上面的i和k的可能进行分析。

分析方向：我们是通过两个不等式进行锁定i,k的，所以问题可能出现的原因就是不等式这里。

****1.对于某个B[j]，所有的A都大于。--解决：判断A[0]>B[j],直接continue本次j。

       2.对于某个B[j],  所有的A都小于。--解决：判断A[-1]<B[j],直接i=n-1即可。

       3.对于某个B[j],  所有的C都大于。--解决：判断C[0]>B[j],直接k=0即可。

       4.对于某个B[j],  所有的C都小于。--解决：判断C[-1]<B[j],直接continue本次j.

~~~~~~~~~~~~~~~~~~~~代码实现~~~~~~~~~~~~~~~~~~~~~~~

一一一一python代码：

n=eval(input())

A=list(map(int,input().split(" ")))

B=list(map(int,input().split(" ")))

C=list(map(int,input().split(" ")))

A.sort()

B.sort()

C.sort()

ans=0

for j in range(n):

    i=n

    k=0

    b=B[j]

    if A[-1]>=b:

        if A[0]>=b:

            continue

        for p in range(0,n-1):

            if A[p]=b:

                i=p

                break

    else:

        i-=1

    if C[0]<=b:

        if C[-1]<=b:

            continue

        for p in range(1,n):

            if C[p]>b and C[p-1]<=b:

                k=p

                break

    else:

        k=0

    ans=ans+(i+1)*(n-k)

print(ans)

二二二二二C语言代码：

#include

//辅助函数，交换值

void change(int *a,int *b){

int temp=*a;

*a=*b;

*b=temp;}

//划分函数

int partition(int ls[],int low,int high){

int i=low-1;

int j=high;

int pivot=ls[high];//枢纽 

while(1){

while(ls[++i]<pivot);

while(ls[--j]>pivot);

if (i<j)

//交换值

change(&ls[i],&ls[j]); 

else

    break;

}

//把枢纽放到正确的位置上 

change(&ls[i],&ls[high]);

return i;

} 

//快速排序

void qsort(int ls[],int low,int high){

if (low<high){

int mid=partition(ls,low,high);

qsort(ls,low,mid-1);

qsort(ls,mid+1,high);

}

} 

//快速排序入口 

void quick_sort(int ls[],int n){

qsort(ls,0,n-1);

}

int main(){

int n,i; 

scanf("%d",&n);

int A[n],B[n],C[n];

for (i=0;i<n;i++)

    scanf("%d",&A[i]);

for (i=0;i<n;i++)

    scanf("%d",&B[i]);

for (i=0;i<n;i++)

    scanf("%d",&C[i]);

quick_sort(A,n);

quick_sort(B,n);

quick_sort(C,n);

int ans=0,j;

for (j=0;j<n;j++){

int i=n,k=0,b=B[j],p;

if (A[-1]>=b){

if (A[0]>=b)

    continue;

for (p=0;p<=n-1;p++){

if (A[p]=b){

i=p;

break;}}}

else{

i=i-1;}

if (C[0]<=b){

if (C[-1]<=b)

   continue;

for (p=1;p<n;p++){

if (C[p]>b &&C[p-1]<=b){

k=p;

break;}}}

else{

k=0;}

ans+=(i+1)*(n-k);

}

printf("%d",ans);

return 0;

}

////////-----------方法反思！！！！！！！！！！

我们每一次，对于B[j]，我们都要对A，C从头遍历寻找满足的i和k，无疑这里面我们会做大量的重复的无效的工作！！！

我可以使用备忘录，对于每次的j，它的B[j]前一个B[j-1],会存在一个i和k的值，那我们完全可以利用起来。

先分析，对于B[j-1]的i和k,

一：对于i：存在A[i]

二：对于k:同样的分析可知，C[k]>B[j-1]&&C[k-1]<=B[j-1]，对于B[j]的,一定有C[k-1]

下面实现修改：

--------python:

n=eval(input())

A=list(map(int,input().split(" ")))

B=list(map(int,input().split(" ")))

C=list(map(int,input().split(" ")))

A.sort()

B.sort()

C.sort()

ans=0

fin=[0,1]#####备忘录记录

for j in range(n):

    i=n

    k=0

    b=B[j]

    if A[-1]>=b:

        if A[0]>=b:

            continue

        for p in range(fin[0],n-1):###修改一

            if A[p]=b:

                i=p

                fin[0]=i###第二处，更新即可

                break

    else:

        i-=1

    if C[0]<=b:

        if C[-1]<=b:

            continue

        for p in range(fin[1],n):####第三处

            if C[p]>b and C[p-1]<=b:

                k=p

                fin[1]=k####第四处

                break

    else:

        k=0

    ans=ans+(i+1)*(n-k)

print(ans)

-------C语言：

同理即可，

int fin[2]={0,1};

,,,,,,,

,,,,,,

,,,,,

,,,,,

即可