P2564. 热点网站统计

解题思路

显然是考察排序的一道题目。

每一行的输入只会是两种情况：

• 输入 URL，表示某一网站访问过
• 输入数字 N，表示需要返回访问次数 Top N 的那些网站，并且对它们进行排序

注意到每次输入 URL 的时候，都需要重新更新它的访问次数，这很明显可以使用哈希表来完成关于访问次数的统计。此外，由于输入的长度不定，因此需要使用 try-except 异常处理语句来进行编写输入。

因此整体的代码框架如下：

剩下的内容就是要处理代码中，关于输入之后的排序部分。

注意到我们首先要按照出现频次降序排列，相同频次的再按照字典序升序排列。排序的对象为 cnt 中的这些 key（若干的 URL）组成的列表，故对应的 lambda 函数为：

如果再加上取前 N 个的切片操作，以及用 "," 进行合并为字符串，再将字符串存入 ans 中，则代码为：

把上述代码放入上述代码框架中的 pass 部分，就基本完成了本题。

本题涉及到的动态排序过程，最优的解法实际上是使用堆/优先队列来解决。感兴趣的同学可以自己去尝试一下。

复杂度分析 设输入总行数为 L，其中查询（数字行）共 q 次，处理到某次查询时哈希表里的不同 URL 数为 k（k 不超过此前 URL 行的总数）。

• 每读入一个 URL：哈希表计数加一，均摊 O(1)（严格说是 O(URL 长度)，用于计算哈希）。
• 每次查询：对当前全部 k 个不同 URL 排序，O(k log k) 次比较，每次比较涉及次数整数与 URL 字符串的字典序，随后取前 N 个拼接为 O(N)。

因此总时间复杂度为 O(L + q·k log k)，瓶颈在每次查询都对全量 URL 重新排序；思路末尾提到的堆/优先队列正是针对这一点的优化方向。空间上哈希表保存 k 个 URL 及其计数，按 URL 总字符数计为 O(k)。

边界与注意事项

• 输入行数不确定：Python 版用 while 循环配合 try-except，读到输入结束（input() 抛出异常）时跳出；C++ 版用 while (getline(...)) 在读入失败时自然结束，两者等价。
• 区分两类行的依据：Python 用 item.isdigit() 判断整行是否全为数字；C++ 只看首字符 isdigit(input[0])。
• 查询的 N 可能大于当前不同 URL 的个数：Python 的切片 temp[:N] 超界时自动截断，C++ 的循环条件里也带了 i < sortedCnt.size() 的判断，都不会越界。
• 并列规则：访问次数相同的 URL 按字典序升序排列（排序键中的第二关键字 x）。
• 每次查询只基于此前已输入的访问记录，结果先存入 ans，全部输入处理完后再统一逐行输出。