【P11840】 错位排列

Question

提交
0.07K

通过
0.03K

时间限制
1000MS

内存限制
128MB
给定一个 [1,n]的排列，要求你构造一个新的 [1,n] 的排列，使得这两个排列之间的任意一个相同位置的元素都不相同，且满足这个排列的字典序最小。 如果无法构造出这样的序列则输出−1

输入格式
第一行t（1≤t≤200），表示t组测试数据。

每组测试数据的第一行n（1≤n≤1000）表示本组数据的个数，第二行有n个数，表示当前排列情况

输出格式
对于每个测试用例，输出n个正整数，即字典顺序上最小的符合要求的排列。如果不存在，则输出−1。

输入样例#1
4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1
输出样例#1
2 3 1
1 2 3 4 5
1 2 4 3
-1

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

这个问题是一个典型的错位排列问题，也称为德利克雷排列。解决这个问题的一个常见方法是使用递归或回溯算法。下面是一个可能的C++实现方法：

1. 读取输入：首先读取测试数据的数量 t，然后对于每组数据，读取序列长度 n 和序列本身。
2. 检查序列长度：如果 n 为1，直接输出 -1。
3. 构造新序列：使用回溯算法尝试构造一个满足条件的新序列。
4. 输出结果：如果成功构造出新序列，则输出这个序列；否则输出 -1。

下面是具体的C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 用于检查当前排列是否满足条件
bool isValid(vector<int>& arr, int n, int index) {
    for (int i = 0; i < index; ++i) {
        if (arr[i] == arr[index]) {
            return false;
        }
    }
    return true;
}

// 回溯算法构造新序列
bool backtrack(vector<int>& arr, vector<int>& res, int n, int index) {
    if (index == n) {
        return true;
    }

    for (int i = 1; i <= n; ++i) {
        if (isValid(arr, n, i) && res[i - 1] != arr[i - 1]) {
            res[i - 1] = arr[i - 1];
            if (backtrack(arr, res, n, index + 1)) {
                return true;
            }
            res[i - 1] = 0; // 回溯
        }
    }

    return false;
}

// 主函数
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            cin >> arr[i];
        }

        if (n == 1) {
            cout << "-1" << endl;
            continue;
        }

        vector<int> res(n, 0);
        if (backtrack(arr, res, n, 1)) {
            for (int i = 0; i < n; ++i) {
                cout << res[i] << " ";
            }
            cout << endl;
        } else {
            cout << "-1" << endl;
        }
    }
    return 0;
}

代码解释：

• isValid 函数用于检查当前位置的元素是否与之前的位置相同。
• backtrack 函数是一个回溯算法，尝试在每个位置放置一个不同的数字，并递归地处理下一个位置。
• main 函数读取输入数据，并调用 backtrack 函数来构造新序列。

这种方法的时间复杂度较高，尤其是在 n 较大时，可能需要优化以满足时间限制。不过，对于题目中给定的 n ≤ 1000 的限制，这种方法通常是可行的。