CF847E Packmen

一个游戏场地是一个 $1 \times n$ 的方格带。在一些格子里有吃豆人（Packman），在一些格子里有星号，其他格子为空。 吃豆人可以在 $1$ 个时间单位内移动到相邻的格子。如果目标格子里有星号，吃豆人会吃掉它。吃豆人吃星号不需要花时间。 在初始时刻，所有吃豆人开始移动。每个吃豆人可以无限次改变移动方向，但不允许走出游戏场地边界。吃豆人之间不会相互干扰；一个格子可以有任意数量的吃豆人在任意方向移动。 你的任务是确定吃豆人吃掉所有星号所需的最少时间。

第一行包含一个整数 $n$（$2 \leq n \leq 10^{5}$），表示游戏场地的长度。 第二行包含一个长度为 $n$ 的字符串，描述这个游戏场地。如果第 $i$ 个位置是符号 '.'，则第 $i$ 个格子为空；如果是符号 '*'，则第 $i$ 个格子有一个星号；如果是符号 'P'，则第 $i$ 个格子有一个吃豆人。 保证场地上至少有一个吃豆人和至少有一个星号。

输出吃豆人吃掉所有星号所需的最少时间。

在第一个样例中，位置 $4$ 的吃豆人会向左移动并吃掉位置 $1$ 的星号，他将花费 $3$ 个时间单位。同时，位置 $6$ 的吃豆人会吃掉它相邻的所有星号。例如，它可以先向左移动，$1$ 个时间单位后吃掉位置 $5$ 的星号，然后从位置 $5$ 向右移动，$2$ 个时间单位后吃掉位置 $7$ 的星号。所以在 $3$ 个时间单位内，吃豆人能吃掉所有星号。 在第二个样例中，位置 $4$ 的吃豆人会向左移动，$2$ 个时间单位后吃掉位置 $2$ 和 $3$ 的星号。位置 $5$ 和位置 $8$ 的吃豆人会向右移动并分别在 $2$ 个时间单位内吃掉位置 $7$ 和 $10$ 的星号。因此，$2$ 个时间单位足够吃豆人吃掉所有星号。 由 ChatGPT 5 翻译