题解 | #合唱队#

#合唱队#

此题是最长递增子序列的变体，基本思路是对原序列从左到右和从右到左分别求出到每个元素的最长递增子序列的长度。例如，原序列为长度为N的序列[8,20,12,15,10,9]，从左至右的到序列里每个元素的最长递增子序列为l1=[1,2,2,3,2,2]，从右至左为l2=[1,4,3,3,2,1]，l1+l2=[2,6,5,6,4,3]。那么合唱队最长队伍是L = max(l1+l2)-1，减1是因为计算l1和l2时重复计算了一次元素本身。因此最少出列人数为原序列长度N-L。

此题关键在于求出l1，l2。可由动态规划求出。用dp[i]表示从左至右到原序列第i个元素的最长递增子序列的长度，从第i个元素往回遍历更新dp[i]的值。由于每个元素都需要往回遍历一次，时间复杂度是o(n^2)。往回遍历如何更新dp[i]的值在其他题解已有很好的介绍，这里主要写用二分法代替往回遍历的过程，时间复杂度是o(nlogn)。

二分法的过程为：首先创建数组arr=[ele_1]，ele_1是原序列第一个元素，然后从第二个元素开始从左至右遍历原序列

1. 如果ele_i > max(arr)，将ele_i加到arr最后
2. 如果ele_i <= max(arr)，用二分法找到arr中第一个比ele_i大（或相等）的元素并用ele_i替换

遍历完成后arr的长度即为最长递增子序列的长度（但arr不是最长递增子序列）。第二步替换是因为为遍历到的元素可能会有比ele_i大但比替换元素小的元素，比如原序列为[2,5,8,3,4,6]。

import bisect
def inc_max(l):
    dp = [1]*len(l) # 初始化dp，最小递增子序列长度为1
    arr = [l[0]] # 创建数组
    for i in range(1,len(l)): # 从原序列第二个元素开始遍历
        if l[i] > arr[-1]:
            arr.append(l[i])
            dp[i] = len(arr)
        else:
            pos = bisect.bisect_left(arr, l[i]) # 用二分法找到arr中第一个比ele_i大（或相等）的元素的位置
            arr[pos] = l[i]
            dp[i] = pos+1
    return dp 

while True:
    try:
        N = int(input())
        s = list(map(int, input().split()))
        left_s = inc_max(s) # 从左至右
        right_s = inc_max(s[::-1])[::-1] # 从右至左
        sum_s = [left_s[i]+right_s[i]-1 for i in range(len(s))] # 相加并减去重复计算
        print(str(N-max(sum_s)))
    except:
        break