← Go Back

Make UTPC

题目大意

给定一个由字符 U、T、P、C 组成的长度为 $N$$N$ 的字符串 $S$$S$。你可以随意次数地进行以下操作：选择整数 $i,j(1\le i<j\le N)$$i,\ j\ \,\ (1\ \leq\ i\ <\ j\ \leq\ N)$，交换字符串 $S$$S$ 中第 $i$$i$ 个字符和第 $j$$j$ 个字符。

求使字符串 $S$$S$ 满足以下条件所需要的操作次数的最小值：$S$$S$ 作为连续子串包含 UTPC。

注意：$S$$S$ 至少包含一个 U、T、P 和 C。

输入从标准输入以下格式给出： $N$$N$ 和 $S$$S$

输出满足条件所需要的操作次数的最小值。注意要输出换行。

• $4\le N\le 10000$$4\ \leq\ N\ \leq\ 10000$

• $S$$S$ 是由 U、T、P、C 组成的长度为 $N$$N$ 的字符串

• $S$$S$ 至少包含一个 U、T、P 和 C

题目分析

题目要求在给定字符串 $S$$S$ 上进行一些操作，使得它包含一个连续子串 UTPC。这可以转化为求最少需要多少次交换操作才能达到目标。

一种朴素的做法是暴力枚举所有可能的子串，判断是否包含 UTPC，从中选出长度最小的子串，然后计算交换次数。这种方法的时间复杂度为 $O(n^3)$$O(n^3)$，无法通过本题。

考虑优化上述方法。如果我们已经找到了一个包含 UTPC 的子串，那么只需要将其左侧和右侧的字符逐步移动，就可以让这个子串恰好成为一个以 U 开头、以 C 结尾的连续子串。因此，我们只需要在原始字符串中寻找到这样一个三元组 $(i,j,k)$$(i, j, k)$，其中：

• $i$$i$ 表示第一个出现的 U 的位置；

• $j$$j$ 表示第一个出现的 T 或者 P 的位置，并且满足 $j>i$$j > i$；

• $k$$k$ 表示第一个出现的 C 的位置，并且满足 $k>j$$k > j$。

然后我们就可以对这个子串进行移动，使得它恰好成为一个以 U 开头、以 C 结尾的连续子串。具体地，我们首先把 U 和 T（或者 P）之间的字符全部移到 U 之前，再把 C 和其它字符之间的字符全部移到 C 之后，这样整个子串就变成了 UTPC。

至于如何计算交换次数，可以使用类似快排中的算法来实现。具体来说，我们维护两个指针 left 和 right，分别指向当前未处理的子串的左端点和右端点。每次操作时，我们先找到第一个不满足条件的字符，例如左边第一个不是 U 或者 T 的字符和右边第一个不是 P 或者 C 的字符。如果它们之间距离为 $d$$d$，那么我们就需要执行 $d$$d$ 次交换操作，把它们逐一交换。显然，这个过程的时间复杂度为 $O(n)$$O(n)$。

综上所述，我们可以用 $O(n^2)$$O(n^2)$ 的时间复杂度解决本题。