自动搬运

查看原文

来自洛谷，原作者为

	Piwry 空想上の人格保持者

搬运于2025-08-24 22:19:31，当前版本为作者最后更新于2020-12-01 19:51:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解析

首先考虑 $a_i$ 均不相同时该怎么做

考虑将 $\{a_i\}$ 排序得到 $\{b_j\}$，并记录每个值在排序前所在的位置，将排序后的位置 $j$ 与排序前的位置 $i$ “连边” $(i, j)$。不难发现这样得到的图是由多个环组成的，其中每条边 $(u, v)$ 代表位置在 $u$ 的元素需要交换到位置 $v$，每个环（忽略自环）可以用一次操作完成

一个想法是对每个环做一次操作，操作中选择的下标数量的和就是所有操作环的大小的和 $\texttt{sum}$；不难发现操作中每次元素的交换都是必要的，因此 $\texttt{sum}$ 就是有解时 $s$ 的下界

但如果 $s$ 足够大，直接对每个环做一次操作是错的；可以想到可以用一次操作将多个环 “连” 在一起，这样就可以将多次操作简化为 $2$ 次。具体来说，合并 $k$ 个环的代价是多选择 $k$ 个下标

这样排列的情况就做完了

接着考虑 $a_i$ 可能相等的情况。这时主要的难点是在于每个 $a_i$ 排序完成后合法的位置可能有多个；即我们可以在一定程度上操纵连边后图的形态，从而使得图中的环更少

设想将所有值相同的 $a_i$ 对应的结点缩成一个点，这样连完边得到的图就是多个强联通分量，且每个结点的入度等于出度。不难发现每个分量都是有欧拉回路的，即可以沿着欧拉回路做一次操作，使得该分量对应的序列元素都到排序后应该待的位置；显然这样做一定是最优的

于是我们的思路就清晰了。至于求出欧拉回路后的做法和排列的情况就差不多了（得到的欧拉回路序列可以直接看做遍历一个环得到的序列）

CODE

一个实现的 trick 是将序列下标作为边 id 标记在边上，这样得到的欧拉回路直接就是一个合法的操作序列；这个具体可见代码

另外由于对于 “合并多个环” 这个操作还需要输出具体的操作序列，其细节的对应关系可能比较火葬场；我的代码有点对着数据调试的感觉qaq，不要深究（可能有时间会回来对这部分补一些注释...）

#include <cstdio>
#include <algorithm>
#include <vector>
using std::sort;
using std::unique;
using std::lower_bound;
using std::vector;
using std::pair;
using std::min;
typedef pair<int, int> pad;

const int MAXN =2e5+20;

/*------------------------------IO------------------------------*/

int read(){
	int x =0; char c =getchar();
	while(c < '0' || c > '9') c =getchar();
	while(c >= '0' && c <= '9') x =(x<<1)+(x<<3)+(48^c), c =getchar();
	return x;
}

void write(const int &x){
	if(x/10)
		write(x/10);
	putchar('0'+x%10);
}

/*------------------------------Map------------------------------*/

vector<pad> E[MAXN];

inline void addedge(const int &u, const int &v, const int &w){
	E[u].push_back(pad(v, w));
}

/*------------------------------Dfs------------------------------*/

vector<int> ans[MAXN];
int tot;

bool vis[MAXN];

void dfs(const int &u){
	vis[u] =1;
	while(!E[u].empty()){
		int v =E[u].back().first, w =E[u].back().second;
		E[u].pop_back();
		dfs(v);
		ans[tot].push_back(w);
	}
}

/*------------------------------Main------------------------------*/

int a[MAXN];

int main(){
	int n =read(), s =read();
	int tmp[MAXN];
	for(int i =0; i < n; ++i)
		tmp[i] =a[i] =read();
	sort(tmp, tmp+n);
	int b[MAXN], col =1;
	for(int i =0; i < n; ++i){
		b[i] =col;
		if(i != n-1 && tmp[i+1] != tmp[i])
			++col;
	}
	unique(tmp, tmp+n);
	for(int i =0; i < n; ++i)
		a[i] =lower_bound(tmp, tmp+col, a[i])-tmp+1;
	for(int i =0; i < n; ++i)
		if(a[i] != b[i])
			addedge(a[i], b[i], i+1);
	// init done. //
	
	int sum =0;
	
	for(int i =1; i <= col; ++i)
		if(!vis[i]){
			dfs(i);
			if(ans[tot].size() != 0){
				sum +=ans[tot].size();
				++tot;
			}
		}
	
	if(sum > s)
		putchar('-'), putchar('1'), putchar('\n');
	else if(s-sum <= 1 || tot <= 1){
		write(tot), putchar('\n');
		for(int i =0; i < tot; ++i){
			write(ans[i].size()), putchar('\n');
			for(int j =0; j < (int)ans[i].size(); ++j)
				write(ans[i][j]), putchar(' ');
			putchar('\n');
		}
	}
	else{
		int ans_tot =tot-min(s-sum, tot)+2;
		write(ans_tot), putchar('\n');
		for(int i =0; i < ans_tot-2; ++i){
			write(ans[i].size()), putchar('\n');
			for(int j =0; j < (int)ans[i].size(); ++j)
				write(ans[i][j]), putchar(' ');
			putchar('\n');
		}
		vector<int> tmp[2];
		int lst =-1;
		for(int i =tot-1; i >= ans_tot-2; --i){
			tmp[0].push_back(ans[i][ans[i].size()-1-1]);
			ans[i].back() ^=lst ^=ans[i].back() ^=lst;
		}
		ans[tot-1].back() =lst;
		for(int i =ans_tot-2; i < tot; ++i)
			for(int j =0; j < (int)ans[i].size(); ++j)
				tmp[1].push_back(ans[i][j]);
		for(int i =0; i < 2; ++i){
			write(tmp[i].size()), putchar('\n');
			for(int j =0; j < (int)tmp[i].size(); ++j)
				write(tmp[i][j]), putchar(' ');
			putchar('\n');
		}
	}
}