蓝桥杯python递增三元组
第六题
标题:递增三元组
给定三个整数数组
A = [A1, A2, … AN],
B = [B1, B2, … BN],
C = [C1, C2, … CN],
请你统计有多少个三元组(i, j, k) 满⾜:
1.1 <= i, j, k <= N
2. 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 <=1000000<= Ai, Bi, Ci <=100000
【输出格式】
⼀个整数表⽰答案
【样例输⼊】
3
111
222
333
【样例输出】
27
解题思路
这道题对想着⽤暴⼒法的我⾮常不友好
很好分析,遍历三个数组⾥的元素,三层循环,找符合A[i]<B[j]<C[k]的,代码就不提供了,⼀提交,运⾏超时,得分50想想也是,三层循环,超时也合理
改进,先遍历b,再依次遍历a和c,⼀个⽐b⼩,⼀个⽐b⼤
N = int(input())
a = sorted(list(map(int,(input().split()))))
b = sorted(list(map(int,(input().split()))))
c = sorted(list(map(int,(input().split()))))
ans = 0
for i in range(N):
x = 0
y = 0
for j in a:
if j < b[i]:
x+=1
for k in c:
if k > b[i]:
y+=1
ans += x*y
print(ans)
⼀提交,运⾏超时,得分75
这次可以改进的地⽅在于,快速寻找列表元素中⼤于和⼩于指定元素的个数
常规来说,⽤⼆分的思想,但是想着python的优势在于众多的函数库,所以我⽤了这个,将指定元素插⼊到排好序的列表中,返回的是下标
详细的可以参考这篇⽂章,讲bict模块
bict.bict_left()
bict.bict_right()
所以最终代码为
import bict
N =int(input())
a =sorted(list(map(int,(input().split()))))
b =sorted(list(map(int,(input().split()))))
c =sorted(list(map(int,(input().split()))))
ans =0
for i in range(N):
x = bict.bict_left(a,b[i])
y = N - bict.bict_right(c,b[i])
ans += x * y
print(ans)
评测结果正确,得分100