题解：AT_arc124_d [ARC124D] Yet Another Sorting Problem

Link
比较套路。

解法

看到排列，我们直接考虑

i

向

p_i

连边。

注：如果我们这样建边，那么我们容易证明连出来的图由若干个孤立点和环组成。并且，环的点数和边数一致。利用这些性质可以方便地解题。

那么，一次交换操作实际上就对应着图上的两条边

(u_1,v_1),(u_2,v_2)

变为

(u_1,v_2),(u_2,v_1)

。
我们给对应的点染上色，并记环的点数为

size

，分为以下几种情况讨论：

孤立点。这种情况无需考虑，因为已经在正确的位置上了。
异色环。（环上两种颜色的点均存在）这时我们易证操作次数最少为 $size-1$ 。（总能保留一对异色点）
同色环。（环上结点同色）这时如果我们直接交换那么操作次数是 $size+1$ 的。但是我们注意到，如果将一对异色的同色环同时操作，那么操作次数就变成了这两个环的 $size$ 之和。所以这时我们的策略如下：导出所有的黑白同色环，贪心地选取 $size$ 大的环合并，剩下的环直接交换。

CODE：

CPP

//luogu paste jo5j6ogx
cst int N=2e5;
int n,m,last[N+10],tot,p[N+10];
bool col[N+10];
struct edge{
	int u,nxt;
}a[N+10];
il void add(int u,int v){
	a[++tot].u=v;
	a[tot].nxt=last[u];
	last[u]=tot;
}
int siz[N+10],sum[N+10],cnt,ans;
vector<int>vec[2];
bool vis[N+10];
il void dfs(int u){
	if(vis[u]) ret;
	vis[u]=1;
	sum[cnt]+=col[u];siz[cnt]++;
	for(int i=last[u];i;i=a[i].nxt){
		int v=a[i].u;
		dfs(v);
	}
}
int main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	n=read<int>();m=read<int>();
	for(int i=1;i<=n+m;i++){
		p[i]=read<int>();
		add(i,p[i]);
		col[i]=(i>n);
	}
	for(int i=1;i<=n+m;i++){
		if(vis[i]) continue;
		cnt++;dfs(i);
		if(siz[cnt]==1) continue;
		if(sum[cnt]==0) vec[0].emplace_back(siz[cnt]);
		else if(sum[cnt]==siz[cnt]) vec[1].emplace_back(siz[cnt]);
		else ans+=siz[cnt]-1;
	}
	sort(vec[0].begin(),vec[0].end(),[](cst int&x,cst int&y){ret x>y;});
	sort(vec[1].begin(),vec[1].end(),[](cst int&x,cst int&y){ret x>y;});
	int s0=vec[0].size(),s1=vec[1].size(),p0,p1;
	for(p0=0,p1=0;p0<s0&&p1<s1;p0++,p1++) ans+=vec[0][p0]+vec[1][p1];
	for(;p0<s0;p0++) ans+=vec[0][p0]+1;
	for(;p1<s1;p1++) ans+=vec[1][p1]+1;
	write(ans);
	ret 0;
}

Record(Atcoder)

题解：AT_arc124_d [ARC124D] Yet Another Sorting Problem

文章操作

解法

相关推荐

评论

题解：AT_arc124_d [ARC124D] Yet Another Sorting Problem