蓝桥杯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
