P3162. 静态代码扫描服务

解题思路

出题人又不做人了，题目非常费解，需要结合示例和说明仔细理解。

题意理解

首先我们需要理解金币会花在什么地方。主要是两个方面：

• 遇到某一个大小为 N 的文件 file 的时候，如果对它进行扫描，会花费 N 个金币。
• 遇到一个文件后，我们可以选择对文件进行缓存，花费 M 个金币。

缓存的好处是什么呢？ 缓存的好处在于下次再次遇到这个同一个文件 file 的时候，不需要重新扫描花费金币了，可以直接获得其内容。

因此，对于示例二而言：

虽然题目没有给出具体的用例说明，但我们也应该得看懂其含义。 大小为 3 的文件 2 在例子中多次出现了，我们在第一次扫描的时候花费了 3 金币，并且进行缓存花费了 5 金币，之后多次遇到同一个文件 2 都不需要再额外花费金币来扫描了。 文件 5 只出现了一次，因此直接扫描花费 1 金币，不缓存。 一共花费 3 + 5 + 1 = 9 个金币即为答案。

贪心策略

在读懂题意之后，本题的贪心策略其实非常容易想到。 核心的抉择点在于某一个文件在第一次遇到的时候是否要进行缓存。

如果要进行缓存，显然是在第一次遇到的时候就缓存是最划算的，而不是在第二次、第三次遇到的时候才缓存。

由于我们“开了天眼”，知道某一个文件 file 在后续数组中会出现的次数，我们设为 cnt_file。 假设其文件大小（直接扫描所花费的金币数）为 N，如果：

• 不进行缓存操作，对于这个 file 所需要花费的金币即为 N * cnt_file（扫描 cnt_file 次，每次花 N 金币）。
• 进行缓存操作，对于这个 file 所需要花费的金币即为 N + M（扫描 1 次花费 N 金币，缓存 1 次花费 M 金币）。

所以，为了使得对这个 file 的总花费金币更少，我们只需要取上述两个数值之间的较小值即可。 这个过程可以非常方便地使用哈希表来完成。

复杂度分析 设 n 为文件标识序列的长度（即需要处理的文件请求总数），k 为其中互不相同的文件个数（k <= n）。

• 时间复杂度：O(n)。第一个循环遍历 n 个文件请求，每次只做常数次哈希表的查询与更新（平均 O(1)）：文件首次出现时同时登记「每次都扫描」与「扫描一次并缓存」两种累计开销，重复出现时只往前者累加本次扫描费用。第二个循环遍历哈希表中的 k 个不同文件，各取两种开销的较小值累加进答案，为 O(k)，被 O(n) 覆盖。
• 空间复杂度：O(k)，两个哈希表 cost_scan_dic 与 cost_cache_dic 各储存 k 个键值对，另有储存输入序列的 O(n) 数组。