Алгоритм к задаче

Question

Дали задание для решения: суть такова, что имеется N скалолазов, которые во время спуска упали в пещеру и тем самым оказались в ловушке. Чтобы выбраться они могут встать друг другу на плечи и тот скалолаз у которого длина тела и рук достанет до выхода из пещеры может из неё вылезти. Как понимаю есть похожая задача со школьниками в яме, которая решается через жадность и вот суть:

h,l - длина школьника и его рук. H - высота выхода. Для решения сначала сортировал по параметрам h + l и далее брал тех, которые удвл. условию S + h + l <= H то есть, которые доставали до выхода (также копим S += h). Только такое решение не является верным.

Нашел также решение на другом сайте в виде: перебираем школьников в порядке убывания ℎ? + ??, ? уже перебрали, ? выбрались, не выбравшиеся имеют суммарную высоту ?. Получили ?[?, ?] → max.

Что требуется найти: максимальное кол-во выбравшихся из ямы/пещеры людей + их номера (без разницы какой порядок), но это думаю будет просто учесть с помощью структуры.

Буду благодарен за указание на допущенные ошибки или расшифровку последнего решения.

Answer 1

Спасибо за помощь в очередной раз и за минусы!

Код с комментариями:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

//структура человека
struct Prog {
    int num; //номер
    int height; //высота
    int len; //длина рук
};

//компоратор
struct cmp{
    bool operator()(const Prog& a, const Prog& b)const {
        return a.height > b.height; //чтобы получать максимум
    }
};

int main() {
    //получаем данные
    int N, L;
    vector<Prog> mas; //массив людей
    //заполнение
    cin >> N;
    mas.resize(N);
    for (int i = 0; i < N; i++) {
        mas[i].num = i + 1;
        cin >> mas[i].height >> mas[i].len;
    }
    cin >> L;
    //сортируем в порядке увеличения сумм роста и длины рук (жадность)
    sort(mas.begin(), mas.end(), [](const Prog& a, const Prog& b) {
        return (a.height + a.len) < (b.height + b.len);
        });
    //считаем суммарную высоту людей
    int S = 0;
    for (int i = 0; i < mas.size(); i++) {
        S += mas[i].height;
    }
    //динамика
    multiset<Prog, cmp> ms; //ответ
    int sum = 0;
    for (int i = 0; i < mas.size(); i++) {
        //попытка поставить человека в уже существующую очередь
        if (mas[i].len + S - L >= sum) {
            sum += mas[i].height;
            ms.insert(mas[i]);
        }
        else {
            //отсев заранее невыгодных
            if (ms.size() == 0)
                continue;
            //попытка заменить человека на какого-то более рукастого и небольшого роста
            auto max = ms.begin();
            if (mas[i].len + S - L >= sum - max->height && mas[i].height < max->height) {
                sum -= max->height;
                ms.erase(ms.begin());
                sum += mas[i].height;
                ms.insert(mas[i]);
            }
        }
    }
    //вывод результатов
    cout << ms.size() << endl;
    if (ms.size()) {
        for (const auto& i : ms) {
            cout << i.num << " ";
        }
        cout << endl;
    }
    return 0;
}

БЛОГ НА HUSL

Алгоритм к задаче

Ответы (1 шт):