王子豪


私信TA

用户名:utff200341231

访问量:572

签 名:

等  级
排  名 11526
经  验 1023
参赛次数 2
文章发表 1
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

递增三元组

难度:简单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};

,,,,,,,

,,,,,,

,,,,,

,,,,,

即可


 

0.0分

0 人评分

  评论区

  • «
  • »