题解 P6305 【[eJOI2018]循环排序】

· · 题解

解析

首先考虑 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');
        }
    }
}