题解 | #小红的不动点构造#

题解

题目分析

我们需要构造一个长度为 $n$ 的排列，使得恰好有 $k$ 个不动点。不动点是指满足 $a_i = i$ 的位置 $i$ 。

解题思路

观察发现，当 $n - k = 1$ 时，无法构造满足条件的排列。原因如下：

假设有 $k$ 个不动点，那么剩下的 $1$ 个位置不能是不动点
但是剩下的 $1$ 个位置只能放剩下的 $1$ 个数，而这个数必然等于这个位置（因为其他位置都是不动点，剩下的数就是剩下的位置）
所以无法避免这个位置也成为不动点，导致总共有 $k+1$ 个不动点

当 $n - k \neq 1$ 时，我们可以这样构造：

前 $k$ 个位置设为不动点： $1, 2, \dots, k$
中间位置 $k+1$ 不设为不动点，而是放一个较大的数
后面的位置 $k+2$ 到 $n$ 也设为不动点
最后将 $k+1$ 放在最后的位置

这样构造后：

位置 $1$ 到 $k$ ： $a_i = i$ ，是不动点 ✅
位置 $k+1$ ： $a_{k+1} = k+2$ （如果 $n > k+1$ ），不是不动点 ❌
位置 $k+2$ 到 $n-1$ ： $a_i = i+1$ ，不是不动点 ❌
位置 $n$ ： $a_n = k+1$ ，当且仅当 $k+1 = n$ 时才是不动点

总的不动点数量恰好为 $k$ 个。

代码解析

#include <bits/stdc++.h>
using namespace std;
#define f(i, a, b) for (ll i = a; i <= b; i++)
#define fr(i, a, b) for (ll i = a; i >= b; i--)

typedef long long ll;
const int N = 1e5 + 10;
const int Mod = 1e9 + 7;

void solves(){
    ll n, m;  // m 就是题目中的 k
    cin >> n >> m;

    ll cnt = 0;  // 计数器，记录已经输出的元素个数

    // 特判：当 n - m = 1 时，无法构造
    if(n - m == 1) {
        cout << -1;
    } else {
        // 1. 前 m 个位置设为不动点：1, 2, ..., m
        f(i, 1, m) {
            cout << i << " ";
            cnt++;
        }
        
        // 2. 从 m+2 到 n 的位置也设为不动点
        f(i, m + 2, n) {
            cout << i << " ";
            cnt++;
        }
        
        // 3. 如果还剩一个位置，放 m+1
        if(n - cnt == 1) {
            cout << m + 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;  // 题目只有一组测试数据
    while (T--) {
        solves();
    }

    return 0;
}