本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-23 22:27:52

题目大意

给你一个序列，定义一次操作为交换任意两个元素，问最少几次操作使得序列变成单调不降，其中值域为 1~4

思路

我的思路有点奇怪。

一眼看去好像可以先把随便一个 1 先交换到最前面，其次是 2,3,4。然后看一下样例二是对的，然而样例一是错的。

样例一发现有两个 1 可以交换到第一个位置，然而我们随机选了一个，实际上是要把第二个 1 换过来，因为 3 正好换到单调不降后它应该在的位置，就节省了操作。

于是大致思路就出来了，对于每个位置，先优先找当前位置上的数应当在的位置范围内，如果有当前位置应当有的数的话，就优先换过来，否则我们默认换第一个。这个东西直接用一个 set 维护即可。

时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$

我的代码可能实现的并不好，可以自己实现一下试试。

#include <bits\/stdc++.h>
#define N 500005
#define ll long long
using namespace std;
int n,a[N],vis[N];
\/\/这个函数表示找到值为zhi的数在排完序后应在的区间 
pair<int,int> zhao(int zhi) {
	int ans1=0,ans2=0;
	for(int i=1; i<=n; ++i) {
		if(a[i]==zhi) {
			++ans2;
		}
		if(a[i]<zhi) {
			++ans1;
		}
	}
	return make_pair(ans1+1,ans1+ans2);
}
priority_queue<int> s;
pair<int,int> chu[5];
signed main() {
	cin>>n;
	for(int i=1; i<=n; ++i) {
		cin>>a[i];
	}
	\/\/提前预处理一下，方便O(1)查询 
	chu[1]=zhao(1);
	chu[2]=zhao(2);
	chu[3]=zhao(3);
	chu[4]=zhao(4);
	int lst=1,xian=0;\/\/lst表示当前执行到了lst，xian是为了方便遍历 
	int ans=0;
	for(int qwq=1; qwq<=4; ++qwq) {\/\/qwq表示当前已经排序到了值为qwq的数 
		xian=1;
		set<int> ying;
		for(int i=chu[qwq].second+1;i<=n;++i){
			if(a[i]==qwq)
				ying.insert(i);
			\/\/找到应与当前区间换的数 
		}
		int lstt=lst;
		for(;xian<=chu[qwq].second-chu[qwq].first+1; ++lst,++xian) {\/\/先优先找到换之后还能满足的 
			if(a[lst]==qwq)continue;
			auto it=ying.lower_bound(chu[a[lst]].first);
			bool flag=0;
			if(it==ying.end())\/\/没找到 
				flag=1;
			if((*it)>chu[a[lst]].second)\/\/没找到 
				flag=1;
			if(!flag){\/\/交换并删除 
				swap(a[*it],a[lst]);
				ying.erase(it);
				vis[lst]=1;
			}
			++ans;
		}
		for(lst=lstt,xian=1;xian<=chu[qwq].second-chu[qwq].first+1;++lst,++xian){\/\/再次遍历当前区间，换之前没换的 
			if(a[lst]==qwq)continue;
			if(!vis[lst]){\/\/没有被换过就换 
				swap(a[*ying.begin()],a[lst]);
				ying.erase(ying.begin());
				vis[lst]=1;
			}
		}
	}
	cout<<ans;
	return 0;
}