【构造】Codeforces1012E Cycle sort_综合

题意:

给出一个序列，通过一些循环，将其排列成一个不下降的序列。
要求所有循环的长度不超过 $s$ ，并且使得满足条件的情况下，循环的个数尽量少。

分析：

如果不考虑限制条件 $s$ ，很显然，原序列任意一个排列都能在不超过2次循环内求出答案。

构造方法很简单。众所周知，任意一个排列都可以表示成几个不相交的循环。

那么如果长度不为1的循环只有一个，那么只需要这个循环倒过来做一次，就能恢复成原序列。

如果长度不为1的循环有多个，设其分别为
$(p_{i1}、p_{i2}、p_{i3}……p_{ik_i})(p_{i+1\space 1}、p_{i+1\space 2}……p_{i+1\space k_{i+1}})……(p_{m1}、p_{m2}、p_{m3}、……p_{mk_m})$

我们可以将这些循环依次连接，即搞一个
$(p_{i1}、p_{i2}、p_{i3}……p_{ik_i}、p_{i+1\space 1}、p_{i+1\space 2}……p_{i+1\space k_{i+1}}、……p_{m1}、p_{m2}、p_{m3}、……p_{mk_m})$
这么一个大循环，观察一下发现，除了每个循环最后一个元素，其它的都已回到原位。所以我们把所有的最后一个元素再组成一个循环，循环回去就是了。

那么现在来考虑 $s$ 的限制

很显然，每个不再原位的位置，都要被移动至少一次（回到原来的位置）。观察上面的构造方法就能发现，其实这个方法比最小情况多了m而已。设所有不在原位的位置数量为k，如果 $k>s$ ，则一定无解。
反之，如果 $k\leq s-m$ ，那么上述的构造方法就可以实现。
如果 $s-m< k\leq s$ ，那么可以考虑增加一些单纯的循环（即将某个循环倒序）然后使得这个m减少。直至刚好凑到s为止。

现在再来考虑有相等的值的问题。
根据上面的思路，我们需要尽可能减少m，也就是说要尽可能减少循环的个数。

一个很简单的操作方法是，设原序列为 $a_i$ ，将其排序后得到的序列为 $b_i$ ，首先排除掉所有 $a_i=b_i$ 的位置（这些都是已经排好序了的），然后对所有 $a_i$ ，向 $b_i$ 连边。这时可以发现，所有 $a_i$ 相等的位置的顺序任意。所以对不同循环中相等的值，可以通过交换它们以合并成一个循环。这样一来循环的个数就能减少。

所以贪心地想，就需要把所有能合并的循环合并，以得到一个最少的循环覆盖。

细节处理可以使用DSU

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 200010
using namespace std;
int a[MAXN],p[MAXN],n,s;
pair<int,int> b[MAXN];
int fa[MAXN],r[MAXN];
int get_fa(int x){if(fa[x]==0)return x;fa[x]=get_fa(fa[x]);return fa[x];   
}
void merge(int x,int y){int fx=get_fa(x);int fy=get_fa(y);if(fx!=fy)fa[fx]=fy;  
}
bool check(int x,int y){return get_fa(x)==get_fa(y);    
}
int now;
bool used[MAXN];
vector<int> ans[MAXN];
void dfs(int x){used[x]=1;ans[now].push_back(x);if(used[p[x]]==0)dfs(p[x]);
}
int main(){SF("%d%d",&n,&s);for(int i=1;i<=n;i++){SF("%d",&a[i]);b[i]=make_pair(a[i],i); }sort(b+1,b+1+n);for(int i=1;i<=n;i++)p[b[i].second]=i;for(int i=1;i<=n;i++)if(a[i]==b[i].first&&p[i]!=i){p[b[i].second]=p[i];b[p[i]].second=b[i].second;p[i]=i;b[i].second=i;}for(int i=1;i<=n;i++)if(p[i]!=i)merge(p[i],i);int las=0;for(int i=1;i<=n;i++){if(p[b[i].second]==b[i].second)continue;   if(las>=1&&a[las]==a[b[i].second]){int x=las;int y=b[i].second;if(check(x,y))continue;merge(x,y);swap(p[x],p[y]);    }las=b[i].second;}now=0;for(int i=1;i<=n;i++)if(used[i]==0&&p[i]!=i){now++;  dfs(i);}int sum=0;for(int i=1;i<=now;i++)sum+=ans[i].size();if(sum>s){PF("-1");return 0;   }s-=sum;s=min(s,now);if(s<=1){PF("%d\n",now);for(int i=1;i<=now;i++){PF("%d\n",ans[i].size());for(int j=0;j<ans[i].size();j++)PF("%d ",ans[i][j]);puts("");}return 0;}PF("%d\n",now-s+2);for(int i=1;i<=now-s;i++){PF("%d\n",ans[i+s].size());for(int j=0;j<ans[i+s].size();j++)PF("%d ",ans[i+s][j]);puts("");sum-=ans[i+s].size();}PF("%d\n",sum);for(int i=1;i<=s;i++)for(int j=0;j<ans[i].size();j++)PF("%d ",ans[i][j]);PF("\n%d\n",s);for(int i=s;i>0;i--)PF("%d ",ans[i][0]);
}