有一个1到N的排列P,给定P中任意两数的大小关系,求恢复这个排列。 输入说明 第一行一个整数N,接下来N行,每行N个数。 第i行第j列为-1表示Pi<Pj,为1表示Pi>Pj,为0表示Pi=Pj。 1 <= N <= 1000 输出说明 输出一行N个数,表示排列P。 输入样例 5 0 1 1 1 1 -1 0 1 1 1 -1 -1 0 -1 1 -1 -1 1 0 1 -1 -1 -1 -1 0 输出样例 5 4 2 3 1 写出c++代码
时间: 2024-04-09 13:28:03 浏览: 17
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> restorePermutation(int N, vector<vector<int>>& relations) {
vector<int> permutation(N);
// Initialize the permutation with values from 1 to N
for (int i = 0; i < N; i++) {
permutation[i] = i + 1;
}
// Sort the permutation based on the given relations
sort(permutation.begin(), permutation.end(), [&](int a, int b) {
return relations[a-1][b-1] == -1;
});
return permutation;
}
int main() {
int N;
cin >> N;
vector<vector<int>> relations(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> relations[i][j];
}
}
vector<int> permutation = restorePermutation(N, relations);
for (int i = 0; i < N; i++) {
cout << permutation[i] << " ";
}
return 0;
}
```
以上是用C++实现的代码。首先,我们定义一个函数`restorePermutation`来恢复排列。函数接受一个整数N和一个N*N的关系矩阵,在函数内部进行排列的恢复,并返回恢复后的排列。
在`restorePermutation`函数中,我们首先初始化一个长度为N的排列,初始值为1到N。然后,根据给定的关系矩阵,使用`sort`函数对排列进行排序。排序的比较函数使用lambda表达式,根据关系矩阵中的值来判断两个元素的大小关系。
在主函数中,我们首先读取输入的N和关系矩阵。然后调用`restorePermutation`函数恢复排列,并输出结果。
注意:这段代码假设输入的关系矩阵中的值只能是-1、0、1,且排列中的元素从1开始。如果输入的关系矩阵中的值不满足这些条件,可能需要进行适当的修改。