Задача. Седловые точки

Задана матрица $K$, содержащая $n$ строк и $m$ столбцов. Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Найдите количество седловых точек заданной матрицы.

Входные данные

Первая строка содержит целые числа $n$ и $m$. $(1 \leq n, m \leq 750)$. Далее следуют $n$ строк по $m$ чисел в каждой. $j$-ое число $i$-ой строки равно $k_{ij}$. Все $k_{ij}$ по модулю не превосходят $1000$.

Выходные данные

Выведите количество седловых точек.

Тесты

№	Ввод	Вывод
1	2 2 0 0 0 0	4
2	2 2 1 2 3 4	1
3	5 5 100 -100 100 1000 110 10 -1000 100 -1000 110 100 -1000 100 100 110 1000 -1000 1000 1000 100 1000 -1000 1000 1000 -1000	1
4	4 4 1000 1000 100 100 1000 1000 1000 1000 100 100 100 1000 100 1000 1000 1000	4
5	2 3 1 -1 1 0 -1 0	2
6	5 1 -1 0 -1 0 -1	2
7	4 2 1 2 -2 1 -1 2 -2 -1	1
8	3 3 5 1 3 3 1 2 1 1 2	3
7	3 3 5 2 3 3 4 2 1 8 2	0

Решение

Чтобы посчитать количество седловых точек, нужно посчитать совпадения минимумов в каждой строке и максимумов в каждом столбце матрицы.

Вариант решения за $O\left(n^2\right)$

Для этого мы просто сравниваем каждый максимум с каждым минимумом и считаем их совпадения. В этом случае алгоритм будет выполнятся за $O(n^2)$, где $n$ это наибольшая из длин массивов. Это значит что при достаточно больших массивах программа будет работать непозволительно долго. Но такой подход достаточно прост в реализации и интуитивно понятен.

#include <iostream>
#define N 750
using namespace std;
 
int main() {
    int n, m, MIN[N], MAX[N];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int input;
            cin >> input;
            if (i == 0) MAX[j] = input;
            else if (MAX[j] < input) MAX[j] = input;
            if (j == 0) MIN[i] = input;
            else if (MIN[i] > input) MIN[i] = input;
        }
    }
    int count = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (MIN[i] == MAX[j]) count++;
    cout << count;
    return 0;
}

#include <iostream>

#define N 750

using namespace std;

int main() {

int n, m, MIN[N], MAX[N];

cin >> n >> m;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

int input;

cin >> input;

if (i == 0) MAX[j] = input;

else if (MAX[j] < input) MAX[j] = input;

if (j == 0) MIN[i] = input;

else if (MIN[i] > input) MIN[i] = input;

}

int count = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

if (MIN[i] == MAX[j]) count++;

cout << count;

return 0;

}

Вариант решения за $O\left(n\log n\right)$

В этом случае мы сортируем массивы, для установления взаимосвязи между элементами в них. А далее заведя два указателя на элементы массивов проверяем на равенство только не меньшие элементы от текущих в разных массивах. Если равных элементов окажется несколько подряд, то их количество будет равно произведению количества их повторений в каждом из массивов. Дойдя до конца одного из них нужно не забыть проверить остались ли в другом массиве равные последнему в пройденном элементы. Проверять стоит лишь не меньшие элементы. Таким алгоритмом мы проверяем совпадения линейно за $O(n)$, где $n$ это наибольшая из длин массивов, но для него необходимо отсортировать оба массива за $O(n\log n)$. Таким образом мы получаем вычислительную сложность $O(n\log n)$, что уже быстрее предыдущего варианта.

#include <iostream>
#define N 750
using namespace std;
 
void merge_sort(int *arr, int n) {
    if (n == 1) return;
    int len_l = n / 2, len_r = n - len_l;
    int l[len_l], r[len_r];
    for (int i = 0; i < n; i++)
        if (i < len_l) l[i] = arr[i];
        else r[i - len_l] = arr[i];
    merge_sort(l, len_l);
    merge_sort(r, len_r);
    int i = 0, j = 0;
    while (i < len_l && j < len_r)
        if (l[i] < r[j]) arr[i + j] = l[i++];
        else arr[i + j] = r[j++];
    while (i < len_l) arr[i + j] = l[i++];
    while (j < len_r) arr[i + j] = r[j++];
}
 
int main() {
    int n, m, MIN[N], MAX[N];
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int input;
            cin >> input;
            if (i == 0) MAX[j] = input;
            else if (MAX[j] < input) MAX[j] = input;
            if (j == 0) MIN[i] = input;
            else if (MIN[i] > input) MIN[i] = input;
        }
    }
    merge_sort(MAX, m);
    merge_sort(MIN, n);
    int i = 0, j = 0, count_i = 1, count_j = 1, counter = 0;
    while (i < n && j < m) {
        while (i < n-1 && MIN[i] == MIN[i+1]) {
            count_i++;
            i++;
        } 
        while (j < m-1 && MAX[j] == MAX[j+1]) {
            count_j++;
            j++;
        }
        if (MIN[i] < MAX[j]) {
            i++;
            count_i = 1;
        } else if (MIN[i] > MAX[j]) {
            j++;
            count_j = 1;
        } else {
            counter += count_i * count_j;
            i++;
            j++;
            count_i = 1;
            count_j = 1;
        }
    }
    while (i < n && MIN[i] <= MAX[m-1]) {
        while (i < n-1 && MIN[i] == MIN[i+1]) {
            count_i++;
            i++;
        } 
        if (MIN[i] == MAX[m-1]) {
            i++;
            counter += count_i;
            count_i = 1;
        }
 
    }
    while (j < m && MAX[j] <= MIN[n-1]) {
        while (j < m-1 && MAX[j] == MAX[j+1]) {
            count_j++;
            j++;
        } 
        if (MAX[j] == MIN[n-1]) {
            j++;
            counter += count_j;
            count_j = 1;
        }
 
    }
    cout << counter;
    return 0;
}

#include <iostream>

#define N 750

using namespace std;

void merge_sort(int *arr, int n) {

if (n == 1) return;

int len_l = n / 2, len_r = n - len_l;

int l[len_l], r[len_r];

for (int i = 0; i < n; i++)

if (i < len_l) l[i] = arr[i];

else r[i - len_l] = arr[i];

merge_sort(l, len_l);

merge_sort(r, len_r);

int i = 0, j = 0;

while (i < len_l && j < len_r)

if (l[i] < r[j]) arr[i + j] = l[i++];

else arr[i + j] = r[j++];

while (i < len_l) arr[i + j] = l[i++];

while (j < len_r) arr[i + j] = r[j++];

}

int main() {

int n, m, MIN[N], MAX[N];

cin >> n >> m;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

int input;

cin >> input;

if (i == 0) MAX[j] = input;

else if (MAX[j] < input) MAX[j] = input;

if (j == 0) MIN[i] = input;

else if (MIN[i] > input) MIN[i] = input;

}

merge_sort(MAX, m);

merge_sort(MIN, n);

int i = 0, j = 0, count_i = 1, count_j = 1, counter = 0;

while (i < n && j < m) {

while (i < n-1 && MIN[i] == MIN[i+1]) {

count_i++;

i++;

}

while (j < m-1 && MAX[j] == MAX[j+1]) {

count_j++;

j++;

}

if (MIN[i] < MAX[j]) {

i++;

count_i = 1;

} else if (MIN[i] > MAX[j]) {

j++;

count_j = 1;

} else {

counter += count_i * count_j;

i++;

j++;

count_i = 1;

count_j = 1;

}

while (i < n && MIN[i] <= MAX[m-1]) {

while (i < n-1 && MIN[i] == MIN[i+1]) {

count_i++;

i++;

}

if (MIN[i] == MAX[m-1]) {

i++;

counter += count_i;

count_i = 1;

}

while (j < m && MAX[j] <= MIN[n-1]) {

while (j < m-1 && MAX[j] == MAX[j+1]) {

count_j++;

j++;

}

if (MAX[j] == MIN[n-1]) {

j++;

counter += count_j;

count_j = 1;

}

cout << counter;

return 0;

}

Related Images:

Задача

Напишите программу, которая выводит элемент из строки [latex]x[/latex] и столбца [latex]y[/latex] матрицы размера [latex]n × m[/latex], которая заполнена змейкой:

Входные данные

Даны натуральные числа [latex]n[/latex], [latex]m[/latex], [latex]x[/latex], [latex]y[/latex] [latex](1 ≤ x ≤ n ≤ 50, 1 ≤ y ≤ m ≤ 50)[/latex]. Здесь [latex]n[/latex] — количество строк матрицы, [latex]m[/latex] — количество столбцов матрицы, [latex]x[/latex] и [latex]y[/latex] — номера строки и столбца искомого элемента.

Выходные данные

Вывести элемент из строки [latex]x[/latex] и столбца [latex]y[/latex].

Тесты

Входные данные	Выходные данные
[latex]5 \; 2 \; 3 \; 1[/latex]	[latex]4[/latex]
[latex]6 \; 3 \; 4 \; 3[/latex]	[latex]9[/latex]
[latex]10 \; 5 \; 10 \; 2[/latex]	[latex]48[/latex]

Код программы

#include <iostream>
using namespace std;
 
int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    int arr[n][m];
    int num = 0;
    for(int i = 0; i < n; ++i) {
        int dir, j;
        if(i % 2 == 0){
            j = 0;
            dir = 1;
        }
        else {
            j = m-1;
            dir = -1;
        }
        for(; j < m&&j >= 0; j+= dir) {
            arr[i][j] = num;
            ++num;
        }
    }
    cout << arr[x - 1][y - 1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, x, y;

cin >> n >> m >> x >> y;

int arr[n][m];

int num = 0;

for(int i = 0; i < n; ++i) {

int dir, j;

if(i % 2 == 0){

j = 0;

dir = 1;

}

else {

j = m-1;

dir = -1;

}

for(; j < m&&j >= 0; j+= dir) {

arr[i][j] = num;

++num;

}

cout << arr[x - 1][y - 1];

return 0;

}

Решение задачи

Читаем входные данные и объявляем массив $n$ на $m$, $num = 0$ — число элемента в этом массиве, далее будем заполнять его в цикле. Делаем перебор строк, для каждой строки есть число $j$ — номер элемента (в текущей строке), с которого мы записываем числа и число $dir$ — направление, в которое мы эти числа записываем (оно у нас 1 или -1). Если строка четная, то начинаем движение слева направо, если нечетная, то справа налево. Далее перебираем каждый элемент строки и записываем ему свой номер. В ответе выводим выбранный элемент.