题目：AT_abc271_c
链接：洛谷, AT，vjudge

题意

• 有 \(n\) 本漫画书，第 \(i\) 本的有卷数 \(a_i\), 在看漫画前可以执行若干次操作：将任意两本漫画书换成一本任意卷数的漫画书。一个人会按顺序看漫画的第 \(1,2, \dots\) 卷，当他手上没有下一卷要读的漫画时，将会停止阅读。问这个人最多可以读多少本书。

• 数据范围：\(1 \le n \le 3 \times 10^5,1 \le a_i \le 10^9\)。

思路

• 首先如果有重复和编号 \(>n\) 的书卷没有直接使用的意义，可以直接换有用的书卷。具体过程就是先按 \(a_i\) 排序，依次枚举每个编号的书卷，如果有对应的漫画，直接使用。否则如果有没有使用意义的漫画，可以用来换一本当前卷数漫画，否则就只能找书卷编号靠后的漫画换漫画。当凑不出漫画时，模拟结束。

• 时间复杂度

  • 排序：\(O(n \log n)\)
  • 模拟：至多枚举到 \(n\)，\(O(n)\)。
  • 总时间复杂度：\(O(n \log n)\)。