难度:简单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 人评分
WU-输出九九乘法表 (C++代码)浏览:1852 |
WU-输出正反三角形 (C++代码)浏览:1098 |
蚂蚁感冒 (C语言代码)浏览:1408 |
众数问题 (C语言代码)浏览:717 |
快速排序算法1浏览:996 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:419 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:522 |
逆反的01串 (C语言代码)浏览:1528 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:455 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:714 |