← 返回题目列表

AtCoder · arc175_f

F. 追加相同的字符

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

你被给予 N 字符串 S_1, \dots, S_N 由小写英文字母组成。考虑以任意顺序执行以下两种类型的操作零次或多次:

  • 选择一个小写字母 c。追加 c 到年底 S_i 对于所有人 1 \leq i \leq N.
  • 选择一个整数 i 这样 1 \leq i \leq N-1。互换 S_i 和 S_{i+1}.

找出完成任务所需的最少操作总数 S_i \leq S_{i+1} 按字典顺序排列 1 \leq i \leq N-1.

什么是字典顺序?

一个字符串 S = S_1S_2\ldots S_{|S|} 据说是 按字典顺序较小 比字符串 T = T_1T_2\ldots T_{|T|} 如果下面的 1. 或 2. 成立。 在这里, |S| 和 |T| 表示的长度 S 和 T。

  1. |S| \lt |T| 和 S_1S_2\ldots S_{|S|} = T_1T_2\ldots T_{|S|}.
  2. 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 使得以下两者成立:
    • S_1S_2\ldots S_{i-1} = T_1T_2\ldots T_{i-1}.
    • 这封信 S_i 出现在之前 T_i 按字母顺序排列。

约束

  • 所有输入值均为整数。
  • 2 \le N \le 3 \times 10^5
  • S_i 是由小写英文字母组成的字符串。
  • 1 \le |S_i|
  • |S_1| + |S_2| + \dots + |S_N| \le 3 \times 10^5

输入

输入由标准输入按以下格式给出:

N
S_1
S_2
\vdots
S_N

输出

在一行中打印答案。


示例输入 1

5
ab
rac
a
dab
ra

示例输出 1

3

这是一种操作方法。

  • 交换 S_2 和 S_3。现在 (S_1, \ldots, S_5) = (ab, a, rac, dab, ra).
  • 追加 z 到每个字符串的末尾。现在 (S_1, \ldots, S_5) = (abz, az, racz, dabz, raz).
  • 交换 S_3 和 S_4。现在 (S_1, \ldots, S_5) = (abz, az, dabz, racz, raz)。此时,我们有 S_i \leq S_{i+1} 对于所有人 i = 1, \ldots, N-1.

不可能使 S_i \leq S_{i+1} 对于所有人 i = 1, \ldots, N-1 操作少于三个,因此您应该打印 3.


示例输入 2

3
kitekuma
nok
zkou

示例输出 2

0

在执行任何操作之前,我们有 S_i \leq S_{i+1} 对于所有人 i = 1, \ldots, N-1.


示例输入 3

31
arc
arrc
rc
rac
a
rc
aara
ra
caac
cr
carr
rrra
ac
r
ccr
a
c
aa
acc
rar
r
c
r
a
r
rc
a
r
rc
cr
c

示例输出 3

175

请注意,我们可能有 S_i = S_j 为 i \neq j.