题目描述
本题译自 eJOI2018 Problem F「Cycle Sort」
给定一个长为 (n) 的数列 ({a_i}) ，你可以多次进行如下操作：
选定 (k) 个不同的下标 (i_1, i_2, cdots, i_k)（其中 (1 le i_j le n) ），然后将 (a_{i_1}) 移动到下标 (i_2) 处，将 (a_{i_2}) 移动到下标 (i_3) 处，……，将 (a_{i_{k-1}}) 移动到下标 (i_{k}) 处，将 (a_{i_k}) 移动到下标 (i_1) 处。
换言之，你可以按照如下的顺序轮换元素：(i_1 ightarrow i_2 ightarrow i_3 ightarrow cdots ightarrow i_{k-1} ightarrow i_k ightarrow i_1) 。
例如：(n=4, {a_i}={ 10, 20, 30, 40}, i_1=2, i_2=3, i_3=4) ，则操作完成后的 (a) 数列变为 ({ 10, 40, 20, 30}) 。
你的任务是用操作次数最少的方法将整个数列排序成不降的。注意，所有操作中选定下标的个数总和不得超过 (s) 。如果不存在这样的方法（无解），输出 -1。
输入格式
第一行， (2) 个整数， (n) 和 (s (1 le n le 2 imes 10^5, 0 le s le 2 imes 10^5)) 。
第二行， (n) 个整数 (a_1, a_2, a_3, cdots a_n) ，表示数列 ({a_i}) ，其中 (1 le a_i le 10^9) 。
输出格式
如果无解，仅输出 -1 。
否则，第一行输出一个整数 (q) （可以为 (0) ，参见样例 3 ），表示最少需要进行的操作次数。
接下来 (2 imes q) 行描述每次操作。
对于每次操作，先输出一个整数 (k) 表示此操作选定的下标数量，然后在下一行中输出 (k) 个整数 (i_1, i_2, cdots, i_k) 。
在操作次数 (q) 最少的情况下，你可以输出任意一种可行方案。
样例
样例输入 1
5 5
3 2 3 1 1
样例输出 1
1
5
1 4 2 3 5
样例解释 1
你可以用两次操作 (1
ightarrow 4
ightarrow 1) 和 (2
ightarrow 3
ightarrow 5
ightarrow 2) 排序数组，但这样会 WA，因为你的任务是最小化 (q) ，而最优解的 (q=1) 。
一种可行的方法是 (1
ightarrow 4
ightarrow 2
ightarrow 3
ightarrow 5
ightarrow 1) ，即样例输出。
样例输入 2
4 3
2 1 4 3
样例输出 2
-1
样例解释 2
所有操作中选定下标的个数总和的最小值为 (4) （一种可行的方法是 (1 ightarrow 2 ightarrow 1) 和 (3 ightarrow 4 ightarrow 3）)，因此无解。
样例输入 3
2 0
2 2
样例输出 3
0
样例解释 3
数组已经有序，因此不需要进行操作。
样例输入 4
6 9
6 5 4 3 2 1
样例输出 4
2
6
1 6 2 5 3 4
3
3 2 1
样例输入 5
6 8
6 5 4 3 2 1
样例输出 5
3
2
3 4
4
1 6 2 5
2
2 1
补充说明
样例 4 和 5 满足子任务 6 和 7 的限制。
数据范围与提示
| 子任务编号 | 分数 | 限制 |
|---|---|---|
| 1 | $0$ | 样例 |
| $2$ | $5$ | $n, s le 2$ 且 $1 le a_i le 2$ |
| $3$ | $5$ | $n le 5$ |
| $4$ | $5$ | $1 le a_i le 2$ |
| $5$ | $1$$0$ | ${a_i}$ 中 $1$ 到 $n$ 的所有正整数出现且恰好只出现一次， $s=2 imes n$ |
| $6$ | $10$ | ${a_i}$ 中 $1$ 到 $n$ 的所有正整数出现且恰好只出现一次， $n le 1000$ |
| $7$ | $15$ | ${a_i}$ 中 $1$ 到 $n$ 的所有正整数出现且恰好只出现一次 |
| $8$ | $15$ | $s=2 imes n$ |
| $9$ | $15$ | $n le 1000$ |
| $10$ | $20$ | 无特殊限制 |
题解
首先假设没有相同的 (a_i)
离散化一下，对于每个点，如果它错位，那么都把它向它本应该在的地方连边。我们就可以得到很多个环，如果没有要求要操作数最小，那么一种方案就是每个环移动一回，直至最后完成
如果错位个数大于允许操作次数，那么肯定是无解的了
特判掉只有一个环的情况
然后有一种和并环的方法，就是把上面得到的所有的环首尾相接连在一起，最后会发现只有每个环的最后一个位置错位，我们再把这些错位的连成一个新的环操作，所以最少次数就是 (2) 次
但是这样的移动次数是 错位个数 (+) 环数 的，很有可能会超过允许的操作次数，这个时候，我们可以选择不把所有的环合并成一个大环，我们可以把某一些环合并成大环，按照大环的做法去做，而剩下的小环就一个一个自己换，这样可以减少移动次数
所以最后就这样贪心选就好了
如果有相同的 (a_i) 也是一样的，同样的离散化，但找环是在一个欧拉图上找的，直接找欧拉回路
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=200000+10;
int n,s,k,e,a[MAXN],b[MAXN],beg[MAXN],nex[MAXN],to[MAXN],val[MAXN],ext[MAXN],vis[MAXN],use[MAXN],cnt;
std::vector<int> V,ans[MAXN];
std::map<int,int> M;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void discretization()
{
for(register int i=1;i<=n;++i)V.push_back(a[i]);
std::sort(V.begin(),V.end());
V.erase(std::unique(V.begin(),V.end()),V.end());
for(register int i=0,lt=V.size();i<lt;++i)M[V[i]]=i+1;
}
inline void insert(int x,int y,int z)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
val[e]=z;
}
inline void dfs(int x)
{
vis[x]=cnt;
for(register int &i=beg[x];i;i=nex[i])
if(!use[i])
{
int tmp=i;
use[i]=1;
dfs(to[i]);
ans[cnt].push_back(val[tmp]);
}
}
int main()
{
read(n);read(s);
for(register int i=1;i<=n;++i)read(a[i]);
discretization();
for(register int i=1;i<=n;++i)a[i]=b[i]=M[a[i]];
std::sort(b+1,b+n+1);
for(register int i=1;i<=n;++i)
if(a[i]!=b[i])++k,insert(a[i],b[i],i);
if(k>s)
{
puts("-1");
return 0;
}
for(register int i=1;i<=n;++i)
if(!vis[i]&&beg[i])++cnt,dfs(i);
if(cnt<=1||s-k<=1)
{
printf("%d
",cnt);
for(register int i=1;i<=cnt;++i)
{
printf("%d
",ans[i].size());
for(register int j=0,lt=ans[i].size();j<lt;++j)printf("%d ",ans[i][j]);
puts("");
}
return 0;
}
printf("%d
",cnt-min(s-k,cnt)+2);
for(register int i=s-k+1;i<=cnt;++i)
{
printf("%d
",ans[i].size());
for(register int j=0,lt=ans[i].size();j<lt;++j)printf("%d ",ans[i][j]);
puts("");
}
if(s-k)
{
int p1=0,p2=0;
for(register int i=min(s-k,cnt);i>=1;--i)p1+=ans[i].size(),ext[++p2]=ans[i][0];
printf("%d
",p1);
for(register int i=1;i<=min(s-k,cnt);++i)
for(register int j=0,lt=ans[i].size();j<lt;++j)printf("%d ",ans[i][j]);
puts("");
printf("%d
",p2);
for(register int i=1;i<=p2;++i)printf("%d ",ext[i]);
}
return 0;
}