题解 | 合唱队

def binary_search(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left

def solve(n, heights):
    # 计算最长上升子序列(LIS)
    inc = [1] * n
    lis = [float("inf")] * (n + 1)
    lis[0] = float("-inf")

    # O(nlogn)计算LIS
    for i in range(n):
        pos = binary_search(lis, heights[i])
        lis[pos] = heights[i]
        inc[i] = pos

    # 计算最长下降子序列(LDS)
    dec = [1] * n
    lds = [float("inf")] * (n + 1)
    lds[0] = float("-inf")

    # O(nlogn)计算从右到左的LIS，即LDS
    for i in range(n - 1, -1, -1):
        pos = binary_search(lds, heights[i])
        lds[pos] = heights[i]
        dec[i] = pos

    # 找到最长的合唱队形
    max_len = 0
    for i in range(n):
        max_len = max(max_len, inc[i] + dec[i] - 1)

    return n - max_len


# 读取输入
n = int(input())
heights = list(map(int, input().split()))

# 输出结果
print(solve(n, heights))

///////////////////////////////////////////////////////////////////////////////////////////////
for i in range(n):
    # 在lis数组中二分查找第一个大于等于heights[i]的位置
    # 例如：lis = [-inf, 1, 5, inf], heights[i] = 3
    # 此时pos = 2，因为lis[2]=5是第一个大于等于3的数
    pos = binary_search(lis, heights[i])
    
    # 用heights[i]更新lis[pos]
    # 更新后：lis = [-inf, 1, 3, inf]
    # 这保证了lis数组中存储的是最小的结尾元素
    lis[pos] = heights[i]
    
    # inc[i]记录以heights[i]结尾的最长上升子序列的长度
    # pos正好等于这个长度，因为：
    # 1. lis[pos-1]小于heights[i]
    # 2. lis数组前pos-1个位置都被使用了
    # 所以以heights[i]结尾的最长上升子序列长度就是pos
    inc[i] = pos

# 例如对于序列[1,5,3]:
# 初始：lis = [-inf,inf,inf,inf]
# 处理1: pos=1, lis=[-inf,1,inf,inf], inc[0]=1
# 处理5: pos=2, lis=[-inf,1,5,inf], inc[1]=2
# 处理3: pos=2, lis=[-inf,1,3,inf], inc[2]=2
/////////////////////////////////////////////////////////////////////////////////////////////////