Студенты, изучающие C++, готовятся к экспедиции на край света. У них есть корабль, состоящий из сетки, состоящей из

Zvezdopad_Na_Gorizonte

40

следующей строке содержится M целых чисел. Каждое из чисел от 0 до 1000 обозначает грузоподъемность соответствующей ячейки корабля. Затем следует число K (1 ≤ K ≤ 100), обозначающее количество студентов. В следующей строке содержится K целых чисел. Каждое из чисел от 0 до 1000 обозначает массу соответствующего студента. Необходимо вывести максимальное количество студентов, которых можно разместить на корабле без риска утопления.

Для решения этой задачи, мы можем использовать алгоритм жадной стратегии. Нам нужно разместить студентов на корабле, избегая ячеек с грузоподъемностью ниже их массы. Мы будем выбирать ячейки с самой высокой грузоподъемностью и размещать на них студентов по очереди, начиная с самых тяжелых студентов.

Вот пошаговое решение для данной задачи:

1. Считать значения N и M из входных данных.
2. Создать двумерный массив размером N × M для хранения грузоподъемности ячеек.
3. Считать грузоподъемность каждой ячейки и сохранить ее в массиве.
4. Считать значение K из входных данных.
5. Создать массив размером K для хранения массы студентов.
6. Считать массу каждого студента и сохранить ее в массиве.
7. Отсортировать массив с массой студентов в порядке убывания.
8. Создать переменную count, которая будет использоваться для подсчета количества студентов, которых можно разместить на корабле без риска утопления.
9. Пройти по каждому студенту в отсортированном массиве массы студентов:
- Пройти по каждой ячейке корабля:
- Если грузоподъемность ячейки больше или равна массе студента и ячейка не занята, разместить студента на этой ячейке и увеличить count на 1.
- Если грузоподъемность ячейки меньше массы студента, перейти к следующей ячейке.
10. Вывести значение count - максимальное количество студентов, которых можно разместить на корабле без риска утопления.

Давайте реализуем этот алгоритм на языке программирования C++.

cpp

#include 

#include 

#include 



int main() {

    // Шаги 1-6

    int N, M;

    std::cin >> N >> M;

    std::vector> grid(N, std::vector(M));

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

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

            std::cin >> grid[i][j];



    int K;

    std::cin >> K;

    std::vector studentWeights(K);

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

        std::cin >> studentWeights[i];



    // Шаг 7

    std::sort(studentWeights.rbegin(), studentWeights.rend());



    // Шаг 8

    int count = 0;



    // Шаг 9

    for(const auto& weight : studentWeights) {

        for(auto& row : grid) {

            for(auto& cell : row) {

                if(cell >= weight) {

                    count++;

                    cell = -1; // Маркируем ячейку как занятую

                    break;

                }

            }

        }

    }



    // Шаг 10

    std::cout << count << std::endl;



    return 0;

}

Это решение будет работать для заданного входного формата. Вы можете скопировать код и запустить его для проверки задачи.