Question

Месклиниты собрались в экспедицию на край света. У них есть корабль, состоящий из N × M плотиков, связанных между собой. У каждого плотика есть своя грузоподъемность, а у каждого месклинита – своя масса. На каждом плотике может находиться не более одного месклинита. Если грузоподъемность выбранного плотика меньше массы месклинита, то бедный месклинит утонет при посадке. Руководитель экспедиции продумывает рассадку по плотикам. Помогите ему определить, какому максимальному количеству месклинитов удастся отправиться в путь. Входные данные В первой строке даны числа N и M (1 ≤ N, M ≤ 40). В каждой из последующих N строк содержится по M чисел, обозначающих грузоподъемность соответствующего плотика. В (N+2)-ой строке находится число K (1 ≤ K ≤ 2000) – количество месклинитов. В (N+3)-ей строке содержатся K чисел, i-ое из которых – масса i-ого месклинита. Все массы месклинитов и грузоподъемности плотиков – натуральные числа, не превышающие 109. Выходные данные Требуется вывести одно число – максимально возможное количество участников экспедиции. Пример: входные данные 3 2 5 10 7 5 5 5 6 9 5 3 5 12 10 выходные данные 4

Answer 1

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
long long n, m, i, j, k;
cin >> n >> m;
vector < long long > plot, mesk;

for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
{
long long x;
cin >> x;
plot.push_back(x);
}
cin >> k;
for (i = 0; i < k; i++)
{
long long x;
cin >> x;
mesk.push_back(x);
}
sort(plot.begin(), plot.end());
sort(mesk.begin(), mesk.end());

k = 0;
i = plot.size() - 1;
j = mesk.size() - 1;
while (i * j > 0)
{
if (plot[i] >= mesk[j])
{
k++;
i--;
j--;
}
else
j--;
}
cout << k << endl;
}

Answer 2

Для решения данной задачи можно использовать алгоритм жадного выбора.

Сначала создадим двумерный массив размером N x M, в котором будем хранить грузоподъемность каждого плотика. Заполним его значениями из входных данных.

Затем создадим массив размером K, в котором будем хранить массу каждого месклинита. Заполним его значениями из входных данных.

Отсортируем массив масс месклинитов в порядке убывания.

Инициализируем переменную expedition_count, которая будет хранить количество месклинитов, которые смогут отправиться в путь.

Проходимся по каждому месклиниту в отсортированном массиве масс. Для каждого месклинита проверяем, есть ли плотик с грузоподъемностью, которая больше или равна его массе. Если такой плотик найден, увеличиваем expedition_count на 1 и помечаем плотик как занятый.

После прохода по всем месклинитам выводим значение expedition_count.

В данном примере, после выполнения алгоритма, expedition_count будет равно 4, что означает, что максимальное количество месклинитов, которые смогут отправиться в путь, равно 4.