Дана целочисленная матрица [latex]\begin{bmatrix}a_{i,j}\end{bmatrix},i,j=1,..,n[/latex].Получить [latex]b_{1},..,b_{n}[/latex],где [latex]b_{i}[/latex] — это:
[latex]\underset{1\leq j\leq n}{\max a_{ij}}\ * \underset{1\leq j\leq n}{\min a_{ji}}[/latex]Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex] -го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1} = 2[/latex], [latex]b_{2} = 4[/latex].
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ class Ideone { public static void main (String[] args) throws java.lang.Exception{ Scanner in = new Scanner(System.in); int n,maxa,mina; n = in.nextInt(); int a[][] = new int[n][n]; for(int i = 0 ; i < n; ++i){ for(int j = 0; j < n; ++j) { a[i][j] = in.nextInt(); } } int b[] = new int[n]; for( int i = 0; i < n; ++i ) { maxa = a[i][0]; //Придаем максимуму значение первого элемента i-й строки. mina = a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца. for( int j = 0; j < n; ++j ) { maxa = (maxa > a[i][j] ? maxa : a[i][j]); //Вычисляем максимум i-й строки. mina = (mina < a[j][i] ? mina : a[j][i]); //Минимум i-го столбца. } b[i] = maxa * mina; //Наш результат. } for( int i = 0; i < n; ++i ){ System.out.print( b[i] + " " ); } } } |
Тесты
| Матрица порядка [latex]n[/latex], где [latex]n[/latex]: | [latex]a[i][j][/latex] | Результат |
| 2 | [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] | 2 4 |
| 3 | [latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex] | 3 -8 -6 |
Решение
Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ij}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.