P1039 · OFFICIAL SOLUTION

P1039 翻转字符官方题解

Gioush OJ · P1039 翻转字符

翻转字符

【题意简述】

给出字符串 $A$ ，记其翻转串为 $B$ 。每次可以交换 $B$ 中相邻的两个字符，求把 $B$ 变为 $A$ 的最少交换次数。

【Hint】

【提示】

相同字符按出现顺序进行对应不会更劣。建立 $B$ 中每个字符对应到 $A$ 中位置的排列后，答案就是这个排列的逆序对数量。

【数据点 1∼21\sim 21∼2】

用二进制集合 $S$ 表示已经从 $B$ 中取出的位置。令 $k=\lvert S\rvert$ ，下一步枚举 $p\notin S$ 且 $B_p=A_{k+1}$ ，把 $B_p$ 移到未取出字符的最前方。代价是它左侧尚未取出的字符数量。

状态数为 $2^n$ 。时间复杂度为 $\mathcal{O}(n^2 2^n)$ ，空间复杂度为 $\mathcal{O}(2^n)$ 。

【数据点 3∼53\sim 53∼5】

直接维护当前字符串。从左到右处理目标位置 $i$ ，在当前位置之后找到第一个等于 $A_i$ 的字符，再通过相邻交换把它移动到位置 $i$ 。时间复杂度为 $\mathcal{O}(n^2)$ 。

【正解】

先确定重复字符的对应方式。固定字符 $x$ ，设它在 $A$ 中依次出现于

p_1<p_2<\cdots<p_k,

在 $B$ 中依次出现于

q_1<q_2<\cdots<q_k.

可以令 $q_i$ 对应 $p_i$ 。若 $q_i<q_j$ 却分别对应 $p_s>p_t$ ，交换两个相同字符的目标位置不会改变最终字符串，并且会消去这一次交叉。对于任意第三个目标位置，交换也不会增加逆序关系。因此反复消去交叉后，可以得到按出现顺序对应的最优方案。

按照 $B$ 中字符的顺序，依次取出该字符在 $A$ 中尚未使用的最早位置，得到一个排列 $P_1,P_2,\ldots,P_n$ 。

若 $i<j$ 且 $P_i>P_j$ ，这两个字符在初始串与目标串中的相对顺序不同，二者至少交换一次。一次相邻交换只改变一对字符的相对顺序，所以操作次数至少为排列的逆序对数量。

另一方面，按照冒泡排序逐一消去逆序对，每次交换都使逆序对数量减少 $1$ ，最终恰好得到目标顺序。因此最少交换次数就是排列的逆序对数量。

不需要显式构造 $B$ 。先把 $A$ 中每种字符的出现位置从左到右放入队列，再倒序扫描 $A$ ，每次弹出对应队列的队首位置，便可得到排列。随后使用线段树维护已经出现的位置，查询此前加入且大于当前位置的元素数量。

【复杂度分析】

每个位置执行一次查询与一次修改。时间复杂度为 $\mathcal{O}(n\log n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。答案最大为 $\dfrac{n(n-1)}{2}$ ，需要使用 long long。

【参考代码】

1#include <queue>2#include <cstdio>3#define MAXN 2000104using namespace std;5 6int c,n,Line[MAXN],Tree[MAXN<<2];7char Str[MAXN];8queue <int> Pos[26];9 10void Modify(int Now,int l,int r,int x) {11    if (l==r) {12        Tree[Now]=1;13        return;14    }15    int Mid=(l+r)>>1;16    if (x<=Mid) Modify(Now<<1,l,Mid,x);17    else Modify(Now<<1|1,Mid+1,r,x);18    Tree[Now]=Tree[Now<<1]+Tree[Now<<1|1];19}20 21int Query(int Now,int l,int r,int x,int y) {22    if (x>y||l>y||r<x) return 0;23    if (l>=x&&r<=y) return Tree[Now];24    int Mid=(l+r)>>1;25    return Query(Now<<1,l,Mid,x,y)+Query(Now<<1|1,Mid+1,r,x,y);26}27 28int main() {29#ifndef ONLINE_JUDGE30    freopen("flip.in","r",stdin);31    freopen("flip.out","w",stdout);32#endif33    scanf("%d",&c);34    scanf("%d%s",&n,Str+1);35    for (int i=1;i<=n;i++) Pos[Str[i]-'a'].push(i);36    for (int i=n;i>=1;i--) {37        int x=Str[i]-'a';38        Line[n-i+1]=Pos[x].front();39        Pos[x].pop();40    }41    long long Ans=0;42    for (int i=1;i<=n;i++) {43        Ans+=Query(1,1,n,Line[i]+1,n);44        Modify(1,1,n,Line[i]);45    }46    printf("%lld\n",Ans);47    return 0;48}