← 返回题目列表

Codeforces · 962/E

E. 拜特兰、贝尔兰和有争议的城市

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

Byteland 和 Berland 城市位于轴 $$$Ox$$$ 上。另外,这条轴线上还存在有争议的城市,这些城市在他们看来属于各个国家。因此,$$$Ox$$$ 线上有三种类型的城市:

- Byteland 的城市,
- Berland 的城市,
- 有争议的城市。

最近,新一代计算机网络BNET项目已经启动。现在两国的任务就是把城市连接起来,让这个国家的网络连接起来。

各国同意使用 BNET 电缆连接城市对,方式如下:

- 如果您查看 Byteland 的唯一城市和有争议的城市,那么在生成的一组城市中,任何城市都应该可以通过一根或多根电缆从任何其他城市到达,
- 如果您查看 Berland 的唯一城市和有争议的城市,那么在生成的一组城市中,任何城市都应该可以通过一根或多根电缆从任何其他城市到达。

因此,需要选择一组城市对来通过电缆连接,使得这两个条件同时满足。电缆允许双向数据传输。每条电缆恰好连接两个不同的城市。

从一个城市到另一个城市铺设电缆的成本等于它们之间的距离。求铺设一组电缆以连接两个城市子集(Byteland 和有争议的城市、Berland 和有争议的城市)的最低总成本。

每个城市都是 $$$Ox$$$ 线上的一个点。从技术上讲,可以用电缆连接城市 $$$a$$$ 和 $$$b$$$,以便城市 $$$c$$$ ($$$a < c < b$$$) 不连接到该电缆,其中 $$$a$$$、$$$b$$$ 和 $$$c$$$ 同时是城市 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的坐标。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$) — 城市数量。

以下 $$$n$$$ 行包含整数 $$$x_i$$$ 和字母 $$$c_i$$$ ($$$-10^{9} \le x_i \le 10^{9}$$$) — 城市的坐标及其类型。如果该城市属于 Byteland,则 $$$c_i$$$ 等于“B”。如果该城市属于 Berland,则 $$$c_i$$$ 等于 «R»。如果城市有争议,$$$c_i$$$ 等于“P”。

所有城市都有不同的坐标。确保城市按照坐标升序排列。

输出

打印这样一组电缆的最小总长度,如果我们删除所有 Berland 城市 ($$$c_i$$$='R'),则可以找到从任何剩余城市到任何其他剩余城市的方法,仅通过电缆移动。同样,如果我们删除所有 Byteland 城市 ($$$c_i$$$='B'),则可以找到从任何剩余城市到任何其他剩余城市的方法,仅通过电缆移动。

示例

输入 #1

4
-5 R
0 P
3 P
7 B

输出 #1

12

输入 #2

5
10 R
14 B
16 B
21 R
32 R

输出 #2

24

注意

在第一个示例中,您应该将第一个城市与第二个城市连接,第二个城市与第三个城市连接,第三个城市与第四个城市连接。电缆的总长度为 $$$5 + 3 + 4 = 12$$$。

在第二个示例中,没有争议城市,因此您需要连接 Byteland 的所有邻近城市和 Berland 的所有邻近城市。 Berland 的城市坐标为 $$$10, 21, 32$$$,因此要连接它们,您需要两根长度为 $$$11$$$ 和 $$$11$$$ 的电缆。 Byteland 的城市坐标为 $$$14$$$ 和 $$$16$$$,因此要连接它们,您需要一根长度为 $$$2$$$ 的电缆。因此,所有电缆的总长度为 $$$11 + 11 + 2 = 24$$$。