题目描述

本题译自 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 \rightarrow i_2 \rightarrow i_3 \rightarrow \cdots \rightarrow i_{k-1} \rightarrow i_k \rightarrow 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 \times 10^5, 0 \le s \le 2 \times 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 \times 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 \rightarrow 4 \rightarrow 1$ 和 $2 \rightarrow 3 \rightarrow 5 \rightarrow 2$ 排序数组，但这样会 WA，因为你的任务是最小化 $q$ ，而最优解的 $q=1$ 。
一种可行的方法是 $1 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 1$ ，即样例输出。

样例输入 2

4 3
2 1 4 3

样例输出 2

-1

样例解释 2

所有操作中选定下标的个数总和的最小值为 $4$ （一种可行的方法是 $1 \rightarrow 2 \rightarrow 1$ 和 $3 \rightarrow 4 \rightarrow 3）$，因此无解。

样例输入 3

2 0
2 2

样例输出 3

样例解释 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

补充说明

样例 4 和 5 满足子任务 6 和 7 的限制。

数据范围与提示

子任务编号	分数	限制
$1$	$$0$$	样例
$$2$$	$$5$$	$\le 2$$ 且 $\le a_i \le 2$$
$$3$$	$$5$$	$\le 5$$
$$4$$	$$5$$	$\le a_i \le 2$$
$$5$$	$$1$ $0$$	$\{a_i\}$ 中 $$1$$ 到 $$n$$ 的所有正整数出现且恰好只出现一次， $\times n$$
$$6$$		$\{a_i\}$ 中 $$1$$ 到 $$n$$ 的所有正整数出现且恰好只出现一次， $\le 1000$$
$$7$$		$\{a_i\}$ 中 $$1$$ 到 $$n$$ 的所有正整数出现且恰好只出现一次
$$8$$		$\times n$$
$$9$$		$\le 1000$$
		无特殊限制

题解

首先假设没有相同的 $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='\0')
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    if(ch!='\0')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\n",cnt);
        for(register int i=1;i<=cnt;++i)
        {
            printf("%d\n",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\n",cnt-min(s-k,cnt)+2);
    for(register int i=s-k+1;i<=cnt;++i)
    {
        printf("%d\n",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\n",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\n",p2);
        for(register int i=1;i<=p2;++i)printf("%d ",ext[i]);
    }
    return 0;
}

秒客网

【刷题】LOJ 2818 「eJOI2018」循环排序