题目内容

给出一个大小为$N$的数组，数组中的数仅由$1$~$N$组成，且没有重复的元素。

你可以选择相邻两个数进行交换，前提是，每个数最多只能被交换两次。

贪心

题目要求尽量最大的字典序，且每个元素最多只能交换两次。字典序是从前面开始比较的，因此我们也要从前面开始贪心，枚举到第i个的时候，记录max为当前元素，然后往下考虑终止条件就是他的次数足够换到第i个数(j-i<=cnt[j])并记录max，然后从max元素的下标连续交换到i即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
#define N 200005
int a[N];