题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
N = int(input())
a = list(map(int, input().split()))
ans = 0
lf = [1] * (N)
rf = [1] * (N)
# for i in range(1, N):
# for j in range(i):
# if a[j] < a[i]:
# lf[i] = max(lf[i], lf[j]+1)
# for i in range(N-2, -1, -1):
# for j in range(N-1, i, -1):
# if a[j] < a[i]:
# rf[i] = max(rf[i], rf[j]+1)
# TLE
import bisect
lf = [1000000 for _ in range(N)] # 维护最有递增潜力子列
rf = [1000000 for _ in range(N)]
lcnt = [1] # lcnt[i] = n : 第i个人作为中间时, 它左边最多能站几个人构成递增子列
rcnt = [1]
lf[0] = a[0]
for i in range(1, N):
idx = bisect.bisect_right(lf, a[i]) # 这个是<= 需要手动去除=
if idx > 0 and lf[idx-1] == a[i]:
lcnt.append(idx) # 两个人身高一样, 则它们左边站的人数也一样
else:
lf[idx] = a[i]
lcnt.append(idx+1)
rf[0] = a[-1]
for i in range(N-2, -1, -1):
idx = bisect.bisect_right(rf, a[i])
if idx > 0 and rf[idx-1] == a[i]:
rcnt.append(idx)
else:
rf[idx] = a[i]
rcnt.append(idx+1)
rcnt.reverse()
for l, r in zip(lcnt, rcnt):
ans = max(ans, l+r)
print(N-ans+1)
# ps: 会有人身高超过十米?
