bisect是python内置模块,用于有序序列的插入和查找
- 查找: bisect(array, item)
- import bisect
- 若数组a是升序序列
- 使用总结:
bisect.bisect(a,c):返回数组a中最后一个<=c的索引值+1
若c存在于数组a,bisect.bisect_left(a,c)返回数组a中第一个出现c的索引值
若c不存在于数组a,bisect.bisect_left与bisect.bisect等效
若c存在于数组a,bisect.bisect_right(a,c)返回数组a中最后一个等于c的索引值+1
若c不存在于数组a,bisect.bisect_right与bisect.bisect等效
在查询一个有序的数组中有多少个>(<) c的时候,这个函数效率很高
import bisect n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) c=list(map(int,input().split())) a.sort() c.sort() ans = 0 for i in range(n): x=bisect.bisect_left(a,b[i]) y=len(c)-bisect.bisect_right(c,b[i]) ans += x*y print(ans)
这个代码是可以解决蓝桥杯一道真题:三元递增组,相较于用前缀和,代码量大大化简
前缀和代码:
n=int(input()) a=list(map(int,input().split())) b=list(map(int,input().split())) c=list(map(int,input().split())) ans=[0 for i in range(max(a)+1)] for i in a: ans[i]+=1 x=[0 for i in range(max(a)+1)] x[0]=a.count(0) for j in range(1,max(a)+1): x[j]=x[j-1]+ans[j] cns=[0 for i in range(max(c)+1)] for i in c: cns[i]+=1 y=[0 for i in range(max(c)+1)] y[0]=c.count(0) for j in range(1,max(c)+1): y[j]=y[j-1]+cns[j] cnt=0 for k in range(n): if b[k]-1>len(x)-1: p=x[-1] elif b[k]-1<0: p=0 else: p=x[b[k]-1] if len(y)-1<=b[k]: q=0 else: q=y[-1]-y[b[k]] cnt+=p*q print(cnt)
掌握一些内置的高效函数,大有裨益!