time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Bob has a permutation of integers from 1 to n. Denote this permutation as p. The i-th element of p will be denoted as pi. For all pairs of distinct integers i, j between 1 and n, he wrote the number ai, j = min(pi, pj). He writes ai, i = 0 for all integer i from 1 to n.
Bob gave you all the values of ai, j that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given.
Input
The first line of the input will contain a single integer n (2 ≤ n ≤ 50).
The next n lines will contain the values of ai, j. The j-th number on the i-th line will represent ai, j. The i-th number on the i-th line will be 0. It's guaranteed that ai, j = aj, i and there is at least one solution consistent with the information given.
Output
Print n space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them.
Examples
Input
Copy
2
0 1
1 0
Output
Copy
2 1
Input
Copy
5
0 2 2 1 2
2 0 4 1 3
2 4 0 1 3
1 1 1 0 1
2 3 3 1 0
Output
Copy
2 5 4 1 3
Note
In the first case, the answer can be {1, 2} or {2, 1}.
In the second case, another possible answer is {2, 4, 5, 1, 3}.
题解:给了一个方形矩阵,其中第i行第j个数表示原数列第i个数与第j个数的最小值,然后让你求出原数列,这个数列的数属于1-n,且不重复.
分析一下:原数列中,一个数和其他位置的数的最小值,总是小于等于原来的数.比如数列2 5 4 1 3,第一个数2与其他数的最小值总是小于等于2,
所以,我们只要比较方形矩阵中每一行的同一个位置,求出的最大的那个数就是我们要求的数.
例如:
0 2 2 1 2
2 0 4 1 3
2 4 0 1 3
1 1 1 0 1
得到的数列: 2 4 4 1 3,发现4重复了两次,因为5和其他数比的最小值不会等于5,所以我们可以弄个标记数组,发现重复的数就把他加一,所以得到正确的数列: 2 4 5 1 3.
#include <bits/stdc++.h>
const int N=100;
using namespace std;
int a[N];
int m[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int tmp;
scanf("%d",&tmp);
a[j]=max(tmp,a[j]);
}
}
//memset(m,0,60);
// for(int i=1;i<=n;i++) printf("%d %d
",a[i],b[i]);
for(int i=1;i<=n;i++){
m[a[i]]++;
if(m[a[i]]>1) a[i]++;
printf("%d ",a[i]);
} //cout << "Hello world!" << endl;
return 0;
}