2018年第九届蓝桥杯真题解析 | 递增三元组【Python】

问题描述

个人思路

1. 我们对A C数组排序后，分别二分A，C数组；
2. 得到A中小于B[ j ]的数和C中大于B[ j ]的数；
3. 由于 A、C 有序的，那么A数组二分数之前的数和C数组二分数之后的数也满足题意，两数组满足数相乘即可，
4. 遍历数组B即可找到了包含B[ j ]的所有递增三元组的数量

时间复杂度为 O(n(logn))

代码如下 第一种

import os
import sys
def tfind2(l, r, x):
  while l<r:
    mid = (l+r) // 2
    if numlst3[mid] > x:
      r = mid
    else:
      l = mid +1
  return l

def tfind1(l, r, x):
  while l<r:
    mid = (l+r+1) // 2
    if numlst1[mid] < int(x):
      l = mid
    else:
      r = mid - 1
  return l

n = eval(input())
numlst1 = [int(x) for x in input().split()]
numlst2 = [int(x) for x in input().split()]
numlst3 = [int(x) for x in input().split()]
numlst1.sort()
numlst2.sort()
numlst3.sort()

count=0

for i in range(n):
  aa = tfind1(0, n-1, numlst2[i])
  cc = tfind2(0, n-1, numlst2[i])
  if numlst1[aa] >= numlst2[i] or numlst3[cc] <= numlst2[i]:
    continue
  count += (aa+1)*(n-cc)
print(count)

第二种

无赖解法

import bisect
n = eval(input())
numlst1 = [int(x) for x in input().split()]
numlst2 = [int(x) for x in input().split()]
numlst3 = [int(x) for x in input().split()]
numlst1.sort()
numlst2.sort()
numlst3.sort()

count=0
#利用的是二分查找，如果用循环他会说你超时，很有毛病，应该是复杂度要求比较高
for x in numlst2:
   a = bisect.bisect_left(numlst1,x)
   b = n-bisect.bisect_right(numlst3,x)
   count+=a*b