P4724 题解：一级子项最大占用空间

1. 解题思路

本题在**文件路径前缀树（逻辑上按 / 分段）**上做统计：对每个文件，把它的大小累加到「目标目录 target 的一级子项」上。

• 目标是否存在：若存在某个文件路径 p 满足 p == target 或 p 以 target + '/' 为前缀，则认为 target 在文件系统中出现；否则返回空列表。
• 一级子项划分：对满足 p 以 target + '/' 开头的文件，令相对路径 rel = p[len(target)+1:]。若 rel 中不含 /，则该文件本身就是一级子项，累加到 p；否则一级子项为 target + '/' + rel 的第一段路径前缀。
• 目录大小：题意规定目录占用为其内部所有文件大小之和；本题输入只给出文件，因此「一级子目录」的大小等于所有路径以该子目录为前缀的文件大小之和，与上面的累加方式一致。

题目描述

员工 $A$ 的磁盘空间经常被耗尽，他需要找到占用空间最大的目录或文件，然后决定如何清理文件释放空间。

给定某一目录，请编写程序帮助他统计该目录内一级子目录和文件的占用空间，并返回目标目录一级子项（文件或子目录）中占用空间最大的项。

规则说明

1. 目录占用空间为其内部所有文件 $Size$ 的总和，且目录本身 $Size$ 为 $0$。
2. 目录深度不高于 $7$ 层，目录或文件名总长度不超过 $128$ 字节。
3. 当存在多个子项占用空间均为最大时，多个子项采用字符升序排列。
4. 目标目录不在文件系统中时（输入路径前缀匹配不到任何路径），返回空列表。

输入描述

输入： 参数 $1$：要进行统计的目标目录。 参数 $2$：文件系统内的文件列表。 参数 $3$：文件 $Size$ 列表，该列表中的数据和文件列表存在一一对应关系。

输出描述

输出： 目标目录一级子项（文件或子目录）中占用空间最大的项组成的列表。

样例1

输入

"/dir1/dir2-1", ["/dir0/dir1-1/file1-1", "/dir1/dir1-1/file1-1", "/dir1/dir2-1/file3-1", "/dir1/dir2-1/file3-2", "/dir1/dir2-1/dir3-1/file4-1"], [8192, 81920, 2048, 8192, 1024]

输出

["/dir1/dir2-1/file3-2"]

说明

$/dir1/dir2-1$ 下共有三个一级子项 $file3-1$、$file3-2$、$dir3-1$，它们的占用空间统计如下：

• $file3-1$：$2048$
• $file3-2$：$8192$
• $dir3-1$：$1024$，其内部所有文件的 $Size$ 之和，由于内部只有一个文件 $file4-1$，因此和 $file4-1$ 的 $Size$ 一致。

其中 $file3-2$ 占用的空间最大，因此返回 $["/dir1/dir2-1/file3-2"]$。

样例2

输入

"/dir1", ["/dir0/dir2-1/file3-1", "/dir1/dir2-1/file3-1", "/dir1/dir2-1/file3-2", "/dir1/dir2-2/file3-3", "/dir1/file2-3"], [10240, 4096, 8192, 10240, 8192]

输出

["/dir1/dir2-1"]

说明

$/dir1$ 下共有三个一级子项 $dir2-1$、$dir2-2$、$file2-3$，它们的占用空间如下：

• $dir2-1$：$12288$，其内部所有文件的 $Size$ 之和，即 $file3-1$ 和 $file3-2$ 的 $Size$ 相加，结果为 $12288$。
• $dir2-2$：$10240$，其内部所有文件的 $Size$ 之和，即 $file3-3$ 的 $Size$ 为 $10240$。
• $file2-3$：$8192$。

其中 $dir2-1$ 占用的空间最大，因此返回 $["/dir1/dir2-1"]$。

样例3

输入

"/dir1", ["/dir1/dir1/file1", "/dir1/dir1/file2", "/dir1/dir2/file3"], [1024, 2048, 3072]

输出

["/dir1/dir1", "/dir1/dir2"]

说明

$/dir1$ 下共有两个一级子项 $dir1$、$dir2$，它们的占用空间如下：

• $dir1$：$3072$，其内部所有文件的 $Size$ 之和，即 $file1$ 和 $file2$ 的 $Size$ 之和为 $3072$。
• $dir2$：$3072$，其内部所有文件的 $Size$ 之和，即 $file3$ 的 $Size$ 为 $3072$。

由于 $dir1$ 和 $dir2$ 占用的空间一致，且为最大，因此需要对这两个子项进行升序排列后返回，返回结果为 $["/dir1/dir1", "/dir1/dir2"]$。