题解 CF1430E 【String Reversal】
绝顶我为峰
2020-10-12 21:02:56
~~难得切一个 E。~~
~~不过这个确实比较水。/youl~~
题目大意：将一个字符串翻转，每次可以交换相邻两个字符，求最少交换次数。
看到**交换相邻字符**这种操作，自然想到逆序对，显然逆序对的数量就是交换次数。
那么有一个很 naive 的想法就是给每个字符一个目标位置，生成一个目标序列，然后统计一遍这个序列的逆序对就好了。
难点在于这个字符串里是有相同字符的，这样我们直接将 $i$ 的目标位设置成 $n-i+1$ 显然不是最优解（参见样例）
显然，我们的目标就是要生成一个 $1\sim n$ 的排列 $a$，使得 $\forall1\leq i\leq n,stringvalue_i=stringvalue_{a_i}$，且 $a$ 的逆序对数量最少。（**这里认为原串下标是 $1\sim n$**）
那么自然我们想到对于相同字符，把他们的 $a_i$ 倒序赋值就是最优解。
这个结论比较显然，因为序列 $a$ 越接近升序，他的逆序对就越少。
所以我们统计一下每种字母出现位置，同种字母倒序构造目标序列就好了。
置于实现方法，数组 哈希 $vector$ $queue$ $set$ 什么的全都可以。
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#define int long long
string s;
int n,ans,a[200001],b[200001];
vector<int> v[31];
void qqsort(int l,int r)
{
if(l==r)
return;
int mid=(l+r)>>1;
qqsort(l,mid);
qqsort(mid+1,r);
int i=l,j=mid+1,cnt=l-1;
while(i<=mid&&j<=r)
if(a[i]<=a[j])
b[++cnt]=a[i++];
else
{
ans+=mid-i+1;
b[++cnt]=a[j++];
}
while(i<=mid)
b[++cnt]=a[i++];
while(j<=r)
b[++cnt]=a[j++];
for(register int i=l;i<=r;++i)
a[i]=b[i];
}
signed main()
{
scanf("%lld",&n);
cin>>s;
s=" "+s;
for(register int i=1;i<=n;++i)
v[s[i]-'a'].push_back(i);
for(register int i=0;i<26;++i)
for(register int j=0;j<(int)v[i].size();++j)
a[v[i][j]]=v[i][v[i].size()-j-1];//倒序赋值
for(register int i=1;i<=n;++i)
a[i]=n-a[i]+1;//因为前面赋值的是没有经过倒序的位置，所以这里统一倒序
//for(register int i=1;i<=n;++i)
//cout<<a[i]<<endl;
qqsort(1,n);
printf("%lld\n",ans);
return 0;
}
```