题解 | #合唱队#

合唱队问题是要找到一个领唱（leader），他的左侧和右侧分别形成两个单调子序列。

耐心纸牌游戏是求单调子序列的一种高效的求解方法，其复杂度为 O(nlogn)。

输入是一个乱序的牌堆，从中每次抽一张牌，正面朝上摆在桌上，最终要按一定规则摆成一到多堆。最初，抽第一张牌，桌上只有一堆牌；之后的每一张牌，从左到右的各牌堆中，如果值比场上某一堆的牌的最面上的牌小或相等，则抽牌放在符合条件的最左侧牌堆之上，如果不存在这样的堆，则新建一个堆放在现有牌堆的最右侧；直到放完最后一张牌，就可以得到多个有序子串。

用耐心游戏摆出的牌堆的堆数，就是发牌序列所对应的最长递增子列长度。不过，此题需加上限定最后一张牌一定位于该子序列中，此时最后一张发牌所落至堆序数，就是包含它的最长递增子列长度。

以下代码的编码过程中参考了 牛友 sparrow。 的解答 。

import sys
import bisect

num_students = int(input())
students = list(map(int, input().split(" ")))


def play_patience_game(cards) -> list[int]:
    LIS: list[int] = [None] * len(cards)
    piles = []  # 牌堆
    for icard, card in enumerate(cards):  # 发牌
        if icard == 0 or card > piles[-1]:
            piles.append(card)  # 新增一个牌堆
            LIS[icard] = len(piles)
        else:
            pos = bisect.bisect_left(piles, card)
            piles[pos] = card  # 放到牌堆最上面
            LIS[icard] = pos + 1
    return LIS


left = play_patience_game(students)
right = play_patience_game(students[::-1])[::-1]

L = max([(left[leader] + right[leader] - 1) for leader in range(len(students))])

print(num_students - L)