Задача
Задана матрица [latex]K[/latex], содержащая [latex]n[/latex] строк и [latex]m[/latex] столбцов. Седловой точкой этой матрицы назовём элемент, который одновременно является минимумом в своей строке и максимумом в своём столбце.
Найдите количество седловых точек заданной матрицы.
Входные данные
Первая строка содержит целые числа [latex]n[/latex] и [latex]m[/latex]. [latex](1 ≤ n, m ≤ 750)[/latex]. Далее следуют [latex]n[/latex] строк по [latex]m[/latex] чисел в каждой. [latex]j[/latex]-ое число [latex]i[/latex]-ой строки равно [latex]k_{ij}[/latex]. Все [latex]k_{ij}[/latex] по модулю не превосходят [latex]1000[/latex].
Выходные данные
Выведите количество седловых точек.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 2 2 0 0 0 0 |
4 |
| 2 | 3 3 1 2 3 4 3 6 9 5 3 |
0 |
| 3 |
4 4 1 2 0 0 2 2 4 4 0 0 1 1 3 4 2 1 |
0 |
| 4 | 2 2 3 2 1 1 |
1 |
Код программы
|
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 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #define Unknown 1001 using namespace std; int main() { int n, m,uf = 0,maxi; //input cin >> n >> m; int ** x = new int * [n]; for (int i = 0; i < n; i++) x[i] = new int[m]; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> x[i][j]; //workspace int max[m]; for (int i = 0; i < m; i++){ max[i] = Unknown; } for (int i = 0; i < n; i++) { int min = x[i][0]; for (int j = 1; j < m; j++) { if ( min > x[i][j] ) { min = x[i][j]; } } for (int j = 0; j < m; j++) { if (x[i][j] == min) { if (max[j] != Unknown){ maxi = max[j]; } else { maxi = x[i][j]; for (int l = 0; l < n; l++) { if (maxi < x[l][j]){ maxi = x[l][j]; } } max[j] = maxi; } if ( maxi == min) { uf++; } } } } //output cout << uf; return 0; } |
Решение задачи
Для каждой строки, будем осуществлять два прохода. В первом найдем минимальное число, а во втором, если значение очередного элемента будет являться в ней минимумом, то проверим будет ли оно максимумом в своем столбце таким образом, что если элемент заранее созданного массива [latex]([/latex] в котором изначально лежат все [latex]Unknown ([/latex] заранее созданная константа равная [latex]1001[/latex][latex] ([/latex] так как по условию, числа которые мы вводим не больше чем [latex]1000 ) ) )[/latex] не равен [latex]Unknown[/latex], то просто сравним элемент массива с минимумом, иначе найдем максимум для данного столбца и положим его в массив, о котором шла речь ранее и сравним уже это число с минимумом строки. Если они совпадают, то это и есть седловая точка!
Ссылки
Условие задачи на e-olymp.com.
Код решения на ideone.com.
Видите, что бывает если несколько месяцев не учиться?
— Отступы!
— Вычислительная сложность Вашего решения $O\left(n^2m\right)$ вместо логичных $O\left(nm\right).$ Это слишком много. Причиной является то, что Вы заново пересчитываете минимумы в одной и той же строке для каждого элемента. Зачем? Их же можно запомнить в массиве.
Простите, а под «запомнить в массиве» вы имеете ввиду создать новый одномерный массив, в котором мы будем запоминать номера всех минимумов?
Все исправил)
Все сделано, спасибо)
Теперь 1001 стало «волшебным числом». Использовать разбросанный по программе числовые константы, считается плохой практикой. Лучше объявить 1001 как, например, UNKNOWN при помощи директивы препроцессора define.
Принято