题目分析

这是一个基于单词后缀关系的排序优化问题。我们需要找到一种填入单词的顺序，使得总泡椒数最小。

关键观察

1. 后缀关系构成依赖图：如果单词 $A$ 是单词 $B$ 的后缀，那么 $A$ 必须在 $B$ 之前填入，否则代价为 $n \times n$（极大惩罚）

2. 代价计算规则：

   • 情况1：如果存在未填入的后缀单词，代价 = $n^2$（必须避免）
   • 情况2：如果没有后缀单词在已填入列表中，代价 = $x$
   • 情况3：如果有后缀单词在已填入列表中，最大序号为 $y$，代价 = $x - y$

3. 目标：在满足所有后缀依赖关系的前提下，最小化总代价

问题转化

将单词之间的后缀关系建模为有向图：

• 节点：每个单词
• 边：如果 $A$ 是 $B$ 的后缀，则添加边 $A \rightarrow B$（表示 $A$ 必须在 $B$ 之前）

问题转化为：在满足拓扑序的前提下，寻找一种拓扑排序，使得总代价最小。

算法设计

1. 建立后缀关系图

使用字典树（Trie）来高效检测后缀关系：

• 将每个单词反转后插入Trie
• 对于每个单词，在Trie中查找它的所有前缀（即原单词的后缀）

2. 构建依赖图

对于每个单词 $w$：

• 找到所有是 $w$ 后缀的单词
• 建立从这些后缀单词到 $w$ 的边

3. 贪心策略

使用优先队列进行拓扑排序，策略为：

• 总是选择当前可填入的单词中，在已填入列表中拥有最晚后缀的单词
• 这样可以让情况3中的 $y$ 尽可能大，从而减少 $x-y$ 的值

具体实现步骤

1. 预处理：

   • 构建反转单词的Trie
   • 为每个单词记录其后缀单词集合

2. 建图：

   • 创建邻接表表示依赖关系
   • 计算每个节点的入度

3. 拓扑排序：

   • 使用最小堆，按已填入后缀的最大序号排序
   • 维护每个单词的"最近后缀序号"

4. 计算总代价：

   • 按拓扑序依次填入单词
   • 根据规则计算每个单词的代价并累加

复杂度分析

• Trie构建：$O(\text{总字符数})$
• 依赖关系建立：$O(n \times \text{平均单词长度})$
• 拓扑排序：$O(n \log n)$

总复杂度在题目数据范围内可行。

样例分析

对于样例：

2 a ba

后缀关系："a" 是 "ba" 的后缀

最优顺序：先填"a"，再填"ba"

• "a"：情况2，代价 = 1
• "ba"：情况3，最近后缀是"a"(序号1)，代价 = 2 - 1 = 1 总代价 = 2

结论

该问题本质是在依赖关系约束下的排序优化问题，通过建立后缀关系图并采用贪心的拓扑排序策略，可以找到使总泡椒数最小的单词填入顺序。