CF883D Packmen Strike Back

游戏场地由一行 $n$ 个方格组成。在某些格子上有吃豆人，在某些格子上有星号，剩下的格子为空。吃豆人会吃掉星号。 在游戏开始之前，你可以为每个吃豆人选择一个移动方向，向左或向右。一旦游戏开始，所有吃豆人会根据各自的方向同时移动。吃豆人在游戏期间不能改变方向。 当吃豆人进入有星号的格子时，会立刻吃掉该星号。当吃豆人离开该格子后，该格子变为空。每个吃豆人的移动速度为每秒移动 1 个格子。当吃豆人进入边界格子时会停止。吃豆人互不干扰，同一个格子上可以有任意数量、任意方向的吃豆人同时经过。 你的任务是为每个吃豆人指定一个移动方向，使他们能吃掉尽可能多的星号。如果有多种方式能吃掉最多的星号，则应选择用时最短的方案。

第一行包含一个整数 $n$（$2 \leq n \leq 1000000$）—— 游戏场地的格子数。 第二行包含 $n$ 个字符。如果第 $i$ 个字符是 ‘.’，则第 $i$ 个格子为空。如果第 $i$ 个字符是 ‘*’，则第 $i$ 个格子上有星号。如果第 $i$ 个字符是 ‘P’，则第 $i$ 个格子上有吃豆人。 输入保证至少有一个星号和至少有一个吃豆人。

输出两个整数——吃豆人能吃掉的最多星号数量，以及所需的最短时间。

在第一个示例中，最左边的吃豆人应向右移动，最右边的吃豆人应向左移动。所有星号都会被吃掉，最后一个星号会在 4 秒后被吃掉。 由 ChatGPT 5 翻译