T27103: 最短的愉悦旋律长度

greedy, http://cs101.openjudge.cn/practice/27103/

江凯同学推荐了计概A的一个题目，题面如下：

在去年的计概期末，大家知道了P大富哥李哥，而李哥有个好朋友陈哥。

与李哥不同，陈哥喜欢钻研音乐，他创造了一种特殊的音乐，这种音乐可以包含 M 种不同的音符（1 ≤ M ≤ 10000），因此，每个音符都可以唯一编码为 1 到 10000 之间的一个整数。陈哥创作的每首乐曲都可以看做由 N 个（1 ≤ N ≤ 100000）这种音符所组成的音符序列。

例如，可以利用 3 种音符组成如下的音符序列：1,2,2,3,2,3,3,1

根据陈哥敏感的音乐细胞，他发现，针对每首给定的音符序列，有些子序列（不一定连续）会出现在该序列中，而有些子序列则不会出现在该序列中。

例如，对于上面例子中的音符序列，子序列 "1,2,2,1" 就出现在该序列中，而子序列 “2,1,3” 就没有出现在该序列中。

热心的陈哥告诉你：正如子序列"1,2,2,1"一样，子序列中的数不需要在原始音符序列中“连续出现”，只要其遵循原本在音符序列中的先后次序，即使子序列的各个数之间穿插有其他数字，也可认为这个子序列出现于音符序列中。

现在，给定一首已经创作完成的包含 N个音符的音符序列，陈哥想用 M 种不同的音符构造一个子序列，使之“不出现”在给定的乐曲序列中。李哥想将其称为“崭新的旋律”，但陈哥还是喜欢称为“愉悦的旋律”，请问这个“愉悦的旋律”的最短长度是多少？

输入

第1行输入两个整数 N 和 M ，接下来1行输入音符序列。

输出

输出一行，包含一个整数，代表最短的“愉悦的旋律”的长度。

样例输入

14 5
1 5 3 2 5 1 3 4 4 2 5 1 2 3

样例输出

3

# 解释：
所有长度为1和2的可能的子序列都出现了，但长度为3的子序列"2,2,4"却没有出现。

提示：只需要告诉陈哥最短的“愉悦的旋律”的长度就行。

来源：计概A 2023

思路：如果没有n+1套，谁导致n+1套凑不齐

python

N, M = map(int, input().split())
*melody, = map(int, input().split())

cnt = 1
note = set()
for i in melody:
    note.add(i)
    if len(note) == M:
        cnt += 1
        note.clear()

print(cnt)

要去寻找这个“未出现的序列"的最短长度，不妨这样去看待一个问题，以M=3为例，即有3种音符 123。首先这样去想，长度为1的子序列，是不是 1和2和3？长度为2的子序列是不是[123]和[123]两个集合中任选一个？按照前后顺序排起来？长度为3的子序列，是不是集合[123] 和[123] 和[123]三个集合从前往后，每次取一个，按照前后顺序排起来？采用分块出现的思想，那么本题就很清晰了，例如，对于1523444512533，可以分成几个部分，15234/4451253/3，发现，第一个分隔号前，已经出现了1,2,3,4,5一次全部数字，第一个分隔号到第二个分隔号，又出现了1,2,3,4,5，完整的一次？那么我们可以肯定，长度为1和为2的全部子序列已经可以得到，所以只有长度为3的子序列没有被全部枚举，答案就是3。

这是一道经典的贪心算法题目。它的核心思想是利用“分块”来确定子序列的覆盖能力。

1. 代码逻辑解读

核心思想： 如果我们要确保所有长度为 $k$ 的子序列都出现，那么原序列必须能够被划分为至少 $k$ 个阶段，其中每个阶段都包含全部 $M$ 种音符。

原理解析：

第一阶段： 当我们在原序列中从左往右扫描，直到集齐了所有 $M$ 种不同的音符时，我们可以断定：所有长度为 1 的子序列都已经在当前这一段里出现了。
第二阶段： 从第一阶段结束的位置开始，继续往后扫描，直到再次集齐 $M$ 种不同的音符。此时我们可以断定：所有长度为 2 的子序列都出现了。
- 证明： 假设我们要构造任意长度为 2 的子序列 $(a, b)$ 。我们可以从第一阶段中找到最后一个出现的音符，只要它是 $a$ （或者 $a$ 在第一阶段结束前已经出现过），接着在第二阶段中必然能找到 $b$ （因为第二阶段集齐了所有音符）。
依此类推： 如果我们能成功集齐 $k$ 轮完整的 $M$ 种音符，那么所有长度为 $k$ 的子序列都一定存在。
最终结果： 只要我们能集齐 $k$ 轮，那么第 $k + 1$ 轮必然是不完整的（否则就能集齐 $k + 1$ 轮）。因为第 $k + 1$ 轮不完整，说明至少有一个音符在这个阶段没出现，我们利用这个“缺口”就能构造出一个不存在的长度为 $k + 1$ 的子序列。

代码执行流程：

遍历音符序列。
使用一个集合 note 记录当前阶段出现的不同音符。
一旦 len(note) == M，说明一个阶段完成，计数器 cnt 加 1，清空集合开始下一轮。
初始 cnt = 1，因为即使一个阶段都凑不齐，最短的不存在子序列长度也是 1。

2. 代码优化

原代码在逻辑上是完全正确的，但在处理大规模数据（ $N = 10^{5}, M = 10^{4}$ ）时，可以从以下几个方面进行性能和内存优化：

输入效率： Python 的 input().split() 在处理 10 万级数据时较慢，建议使用 sys.stdin.read。
集合操作： 虽然 set 已经很快，但在 Python 中，频繁地 clear() 集合或创建新对象会有开销。如果 $M$ 很大，可以使用布尔数组（或标记数组）配合计数器来替代 set，避免哈希运算。
内存占用： 直接解构整个列表 *melody, = ... 会在内存中存两份数据。

优化后的代码：

python

import sys

def solve():
    # 使用 sys.stdin.read 快速读取所有数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    # 使用迭代器避免一次性产生大列表的副本
    melody = map(int, input_data[2:])
    
    cnt = 1
    # 记录当前阶段已出现的不同音符数量
    found_count = 0
    # 使用标记数组代替 set，索引 i 代表音符 i 是否在当前阶段出现过
    # 数组大小为 M+1 (音符范围 1~M)
    last_seen_in_block = [0] * (M + 1)
    
    # current_block 用来标记当前是第几个阶段，避免重复初始化数组
    current_block = 1
    
    for m in melody:
        if last_seen_in_block[m] < current_block:
            last_seen_in_block[m] = current_block
            found_count += 1
            
            if found_count == M:
                cnt += 1
                found_count = 0
                current_block += 1
                
    sys.stdout.write(str(cnt) + '\n')

if __name__ == "__main__":
    solve()

3. 优化点总结

时间复杂度： $O (N)$ 。由于去掉了 set 的哈希计算，改用数组下标访问，常数项更小，运行速度更快。
空间复杂度： $O (M)$ 。只维护了一个长度为 $M$ 的标记数组，而不需要存储大量的哈希对象。
技巧：current_block 标记法。这是竞赛中常用的技巧，不需要每一轮都用 for 循环把 last_seen_in_block 重置为 0，只需让标识位增加，判断 last_seen_in_block[m] < current_block 即可知道该音符在当前轮次是否出现过。

4. 示例分析

输入：

14 5
1 5 3 2 5 1 3 4 4 2 5 1 2 3

第一阶段：遇到 1, 5, 3, 2，再到 4（中间有重复的 5, 1, 3）。此时集齐 {1,2,3,4,5}。cnt 变为 2。
第二阶段：从后面的 4, 2, 5, 1, 2, 3 中找。集齐 {4, 2, 5, 1, 3}。cnt 变为 3。
序列结束，无法凑齐第三阶段。
输出 3。

这说明：所有长度为 1 和 2 的子序列都存在，但一定存在某个长度为 3 的子序列不存在。

T27103: 最短的愉悦旋律长度 ​

T27103: 最短的愉悦旋律长度