我不会火柴排队

zzc2025 · 2026-11-12 21:14:53 · 题解

交换使得串的前 n 个和后 n 个一样，求交换次数最少。

一样首先得数量一样，我们这里贪心往前面塞，能放则放，容易证明这是正确的。

然后就可以变成两个独立的序列，因为之后在前后之间交换都会是答案不优。

然后我们需要让两个序列的一样，跟火柴排队一样处理就可以了。

但是因为不是排列，对于一样的字母，我们需要让下标小的匹配小的，大的匹配大的，可以用交换证明这样做是正确的，之后对新序列求逆序对就行了。

代码：

#include<bits/stdc++.h>
// #define int long long
#define ll long long
using namespace std;
/*
#pragma region 哈基米
*/
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
inline string reads(){
    string s=" ";char c=getchar();
    while(c>'z'||c<'a') c=getchar();
    while(c>='a'&&c<='z') {s+=c;c=getchar();}
    return s;
}
const int N=2e5+5,S=26;
int n,c[N],p[N],cnt[N];ll ans;vector<int> id[S];int l[S];
struct tree{
    int tr[N];
    #define lb x&(-x)
    void add(int x,int k){while(x<N) tr[x]+=k,x+=lb;}
    int sum(int x){int res=0;while(x) res+=tr[x],x-=lb;return res;}
}tr;
signed main(){
    // freopen("1.in" ,"r",stdin );
    n=read();string s=reads();
    for(int i=1;i<=2*n;i++) cnt[p[i]=s[i]-'a']++;
    for(int i=0;i<S;i++) cnt[i]/=2;
    for(int i=1,k=n+1,j=1;i<=n;i++) {
        c[i]=p[j];ans+=j-i;cnt[p[j++]]--;
        while(!cnt[p[j]]&&j<=2*n) c[k++]=p[j++];
    }
    for(int i=1;i<=n;i++) id[c[i]].push_back(i);
    for(int i=n+1;i<=2*n;i++) c[i]=id[c[i]][l[c[i]]++];
    for(int i=2*n;i>n;i--) {
        ans+=tr.sum(c[i]);tr.add(c[i],1);
    }
    printf("%lld\n",ans);
    return 0;
}