题目翻译

给定长度为 $n$ 的数组 $a$，每次操作可以选取 $k$ 个不同下标 $i_1, i_2, \dots, i_k$，执行循环移位：

$$a_{i_1} \to a_{i_2},\ a_{i_2} \to a_{i_3},\ \dots,\ a_{i_k} \to a_{i_1} $$

目标是用最少的操作次数 $q$ 将数组排序成非降序，且所有操作中涉及的下标总数不超过 $s$。
若不可能，输出 -1。

---

算法思路

问题转化

设当前排列为 $p$，目标排列为 $id$（恒等排列）。
我们可以将当前排列看作一个置换，通过循环移位操作将其变为恒等排列。

关键结论

• 将置换分解为 $c$ 个循环，经典循环排序需要 $c$ 次操作（每个循环单独处理）。
• 若允许一次操作包含多个循环，则可减少操作次数 $q$，但会增加单次操作的下标数。
• 最少操作次数 $q_{\min} = c$。
• 实现 $q_{\min}$ 所需的总下标数 = $n$（所有循环长度之和）。
• 若 $s < n$，则无法在 $q = c$ 次内完成，必须增加操作次数。

构造策略

1. 若 $s \ge n$
   一次操作可处理所有循环（合并成一个大循环），$q=1$。

2. 若 $s < n$

   • 尽量单独处理前 $c - (s - \sum_{i} l_i)$ 个循环（其中 $l_i$ 是循环长度）。
   • 将剩余循环合并成一个或两个大循环，保证总下标数不超过 $s$。
   • 无解条件：即使每次只处理一个循环，总下标数 $n > s$ 时无解。

---

代码步骤解析

1. 输入与离散化

scanf("%d%d", &n, &m); // m 即 s
for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
    allv.push_back(a[i]);
}
sort(b, b + n);
sort(allv.begin(), allv.end());
allv.erase(unique(allv.begin(), allv.end()), allv.end());
for (int i = 0; i < n; i++) {
    a[i] = lower_bound(allv.begin(), allv.end(), a[i]) - allv.begin();
    b[i] = lower_bound(allv.begin(), allv.end(), b[i]) - allv.begin();
}

• 将数组 $a$ 和排序后的 $b$ 离散化，便于处理值到位置的映射。

2. 构建置换图

for (int i = 0; i < n; i++) {
    if (a[i] != b[i])
        vt[a[i]].push_back(make_pair(b[i], i));
    else
        a[i] = i; // 已在正确位置
}

• 对每个值建立边 $(a[i] \to b[i])$，表示当前值应移动到目标值的位置。

3. DFS 找循环

for (int i = 0; i < n; i++)
    if (cur[i] < vt[i].size()) {
        seq.clear();
        dfs(i);
        for (int j = 0; j < seq.size(); j++)
            a[seq[j]] = seq[(j + 1) % seq.size()];
    }

• 通过 DFS 找出值之间的循环，并更新 $a$ 数组为置换形式。

4. 分解位置循环

for (int i = 0; i < n; i++)
    if (a[i] != i && (!vis[i])) {
        vector<int> cur;
        for (int j = i; !vis[j]; j = a[j])
            vis[j] = true, cur.push_back(j), m--;
        cycs.push_back(cur);
    }

• 根据置换 $a$ 分解出位置的循环，同时计算剩余可用下标数 $m$。

5. 判断无解与构造方案

if (cycs.empty()) { puts("0"); return 0; }
if (m < 0) { puts("-1"); return 0; }

• 若已有序，输出 $0$。
• 若剩余下标数不足，输出 -1。

int req = max(0, (int)cycs.size() - m);
for (int i = 0; i < req; i++)
    ans.push_back(cycs[i]);

• 尽量单独处理前 req 个循环，保证总操作次数最少。

if (req < cycs.size()) {
    if (req + 1 >= cycs.size())
        ans.push_back(cycs[req]);
    else {
        vector<int> nw;
        for (int i = req; i < cycs.size(); i++)
            nw.push_back(cycs[i][0]);
        ans.push_back(nw);
        // 调整置换
        int x = a[nw.back()];
        for (int i = nw.size() - 1; i; i--)
            a[nw[i]] = a[nw[i - 1]];
        a[nw[0]] = x;
        // 重新分解循环
        nw.clear();
        nw.push_back(x);
        for (int i = a[x]; i != x; i = a[i])
            nw.push_back(i);
        ans.push_back(nw);
    }
}

• 将剩余循环合并成一个大循环，若合并后仍有多余循环，则再分解一次。

6. 输出答案

printf("%d\n", ans.size());
for (auto &v : ans) {
    printf("%d\n", v.size());
    for (auto &x : v) printf("%d ", x + 1);
    puts("");
}

---

复杂度分析

• 时间复杂度：$O(n)$，每个位置至多访问一次。
• 空间复杂度：$O(n)$，存储循环和临时数组。

---

示例验证

样例 1

5 5
3 2 3 1 1

循环分解后合并为一个操作：

1
5
1 4 2 3 5

样例 2

4 3
2 1 4 3

总下标数至少为 $4$，$s=3$，无解：

-1

样例 3

2 0
2 2

已有序：

0

---

算法标签

• 置换群
• 循环分解
• 贪心构造
• 离散化

---

总结

本题的关键在于：

1. 将排序问题转化为置换循环分解。
2. 通过合并循环减少操作次数。
3. 在 $s$ 限制下贪心分组，保证操作数最少。

该解法高效且符合题目要求，适用于 $n \le 2\times 10^5$ 的大数据范围。