Codeforces 908F - New Year and Rainbow Roads

Author Avatar
Jimmy Zhang Apr 11, 2018
  • Read this article on other devices

太耻辱了!!!

Educational Round 42 中的 E 题就是这道题,然而本辣鸡看一眼就往 MST 去想了。补题的时候偷懒不写题解,那补题还有什么意义?浪费时间?自我安慰?亡羊补牢为时未晚,现在把这道题的题解补上。

题面

一条数轴上有 n (1n300000)n \ (1 \le n \le 300000) 个点,每个点都有一种颜色:红 RR、 绿 GG、 蓝 BB 中的一种。

Roy 和 Biv 想用一些边把这些点连起来。任意两点间都可以连一条边,而连边的长度即两端间的距离。他们希望能使所有点之间联通。

然而,Roy 不能看见红色的点,而 Biv 不能看见蓝色的点。因此,他们希望最终的结果在两人看来都是联通的(即,若删去所有的红点剩余点之间仍然联通,同时若删去所有蓝点剩余点之间仍然联通)。

试求最小边长度之和。

题目链接

贪心!

首先我们不妨对题目进行一些观察:

  • RR 点 和 BB 点间连线是很不划算的,因为两人都看不到;
  • 对于形如 R G RR \ G \ R 的序列,直接连接两个 RR 并不划算。我们完全可以将两个 RR 与中间的 GG 连起来,这样的话边长之和实际上等于直接连接两个 RR,而且还多拖了一个 GG 进来(对于形如 B G BB \ G \ B 的序列也是同理的)。这样一来,我们完全就可以以中间的 GG 为分界线分开考虑左右两个区间了。

这样一分析后解决方法就显而易见了。我们可以将原序列以 GG 为界分割成若干个小序列。我们记小序列的长度为两端 GG 点间的距离:segLen\text{segLen}。对于任意一个小序列,我们有两种可能的连接方式:

  • 两端的 GG 不直接相连,分别联通两端 GG 之间的所有 RR 点 和 BB 点,再将最左和最右的 RR 点 和 BB 点分别与左端 GG 和 右端 GG 相连。这样一来,这个小序列连边的总长度为 2segLen2 \cdot \text{segLen}
  • 两端的 GG 直接相连,这样一来我们就可以不必连接两端 GG 之间相距最远的两个 RR 点(最接近端点的 RR 点与端点 GG 的边也包含在内),同理对于 BB 点也一样。这样一来,这个小序列的长度为:3segLenmaxRedSegLenmaxBlueSegLen3 \cdot \text{segLen} - \text{maxRedSegLen} - \text{maxBlueSegLen}

我们以样例一为例直观地阐述一下两种连接方式:

两种连接方式

我们只需要对于每个小序列算出上述两个值,取较小者加起来就好了。

另外,我们需要单独注意一下没有 GG 点的情况。

参考代码

Submission #33805058

GitHub Backup Link

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/04/11/codeforces-908f/