题解 | #合唱队# 二分查找 O(nlogn)
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
import bisect
n = int(input())
a = list(map(int, input().split()))
lt = [0] * n
rt = [0] * n
st = [] # st[i]表示 所有递增子序列，可以排第i位同学的最低身高；可以证明st自身也是是递增的
for i in range(n):
idx = bisect.bisect_left(st, a[i])
if idx == len(st):
st.append(a[i])
st[idx] = a[i] # 更新可以排第i位同学的最低身高
lt[i] = i - idx
st = []
for i in range(n - 1, -1, -1):
idx = bisect.bisect_left(st, a[i])
if idx == len(st):
st.append(a[i])
st[idx] = a[i]
rt[i] = n - 1 - i - idx
ans = 3000
for i in range(n):
ans = min(ans, lt[i] + rt[i])
print(ans)
投递大疆等公司6个岗位