时间限制： 3000MS
内存限制： 589824KB
题目描述：
小明有一个长度为 n 的正整数序列，序列中每个数字都在范围 [1, k] 内。小明现在想要删除这个序列中的若干数字，使得这个序列的最长上升子序列的长度严格小于 k。他现在想知道：最少需要删除多少个数字？
上升序列是一个长度为 m 的序列 b，满足 b1 < b2 < ... < bm−1 < bm。子序列是指将原序列删除若干位置（或者不删）之后再从左到右拼接起来得到的一个序列。最长上升子序列是指原序列删除最少的位置之后形成的子序列是一个上升序列。例如， [1, 4, 5, 2, 3, 2, 5] 的一个最长上升子序列是 [1, 2, 3, 5]，长度为 4；[1, 2, 3, 4, 5] 的最长上 升子序列就是其本身。
输入描述
第一行一个正整数 T ，表示有 T 组数据。
对于每一组数据，第一行两个正整数 n, k；第二行 n 个正整数 a1, a2, ..., an，表示该序列。
1 ≤ k ≤ n ≤ 105, 1 ≤ T ≤ 5, 1 ≤ ai ≤ k, Σ n ≤ 2 × 105。
输出描述
对于每一组数据输出一行一个非负整数，表示最少需要删除的数字。
样例输入
4
5 3
1 2 3 1 2
5 1
1 1 1 1 1
10 4
1 2 1 2 3 4 3 3 4 4
9 3
1 2 2 1 1 3 2 3 3
样例输出
1
5
2
2
提示
删除的数字用下划线表明。方案可能不止一种。
第一组样例，[1, 2, 3, 1, 2]；
第二组样例，[1, 1, 1, 1, 1]；
第三组样例，[1, 2, 1, 2, 3, 4, 3, 3, 4, 4]；
第四组样例，[1, 2, 2, 1, 1, 3, 2, 3, 3]。
from sortedcontainers import SortedDict
def get_ans(a, b):
count = 0
i, j = 0, len(b) - 1
while i < len(a) and j > -1:
if a[i] > b[j]:
break
else:
count += 1
if i + 1 == len(a) or j - 1 == -1:
i += 1
j -= 1
continue
if a[i + 1] > b[j]:
i += 1
continue
if a[i] > b[j - 1]:
j -= 1
continue
i += 1
return count
时间限制： 5000MS
内存限制： 589824KB
题目描述：
小红遇到了一名粉刷匠。这名粉刷匠有三种颜料，分别是红、黄、蓝。为了方便， 这三种颜料分别命名为 A，B，C。
现在，粉刷匠正在粉刷一面长度为3n 的墙壁。粉刷完之后，三种颜料的数目都相同。由于小红一不小心踢到了颜料桶，使得这面墙的每个地方都被染上了三种颜料中的其中一种，这很让粉刷匠头疼。
粉刷匠每次可以选择一段连续的墙壁进行粉刷，即全部粉刷上同一种颜色（A,B,C 三种中的其中一种）。粉刷匠想知道，他最少需要多少次粉刷才能使得三种颜料的数目都相同？
输入描述
第一行一个正整数 T ，表示有 T 组数据。
对于每一组数据，第一行输入一个正整数 n，表示墙壁的长度为 3n；第二行一个长度为 3n 的字符串，仅包含 ABC 三种字母，表示该墙壁的初始颜色。
1 ≤ n ≤ 5 · 104, 1 ≤ T ≤ 5。
输出描述
对于每一组数据，输出一个整数，表示答案。
样例输入
3
2
ABACBC
3
AAABBBBAC
3
CAACBCBCC
样例输出
0
1
2
提示
对于第一组样例，A,B,C 的数目都是 2，故无需进行粉刷；
对于第二组样例，选择区间 [7, 9] 全部粉刷为 C，之后形成的墙壁为 AAABBBCCC；
对于第三组样例，先选择区间 [4, 4] 粉刷为 B 之后形成的墙壁为 CAABBCBCC， 再选择区间 [9, 9] 全部粉刷为 A 之后形成的墙壁为 CAABBCBCA。此时每种颜色都有 3 个。