Алгоритм выводящий минимальное количество пар, необходимых для удовлетворения всех поступивших заказов

Рейтинг: -3Ответов: 2Опубликовано: 08.02.2023

Нуждаюсь в помощи. Есть задание, но идей как реализовать нету. Буду рад помощи, если не трудно.

Входные данные (2): количество циклопов N; массив N чисел, каждый элемент которого указывает на рекомендованную оптическую силу линзы для каждого i-го Циклопа.

В одном городе на Земле живут Циклопы. У большинства Циклопов есть проблемы со зрением, поэтому им рекомендовано носить контактные линзы. При этом, если Циклопу рекомендовано ношение линз в К диоптрий, его устроят линзы в К-1, К, К+1 диоптрии. Циклопы очень боятся, что о них узнают люди, поэтому заказывают линзы в обычных человеческих магазинах парами одинаковой оптической силы. Один Циклоп решил собирать заказы и оптимизировать процесс закупки линз так, чтобы покупать как можно меньше пар, при этом удовлетворить все поступившие заказы.

Требуется написать алгоритм на javascript, выводящиЙ минимальное количество пар, необходимых для удовлетворения всех поступивших заказов.

Пример: например, для 5-ти Циклопов с диоптриями [1, -1, 2, З, -3], достаточно купить З пары линз (О диоптрий удовлетворят 1-го и 2-го Циклопов, 2 или З диоптрия удовлетворят 3-го и 4-го Циклопов, -2 или -3 или -4 диоптрии удовлетворят 5-го Циклопа, но 1 линза будет не задействована —это нормально).

Ответы

▲ 2

Одна из разновидностей задачи покрытия.

Создадим массив пар требуемых отрезков оптической силы для циклопов. Для каждого циклопа добавляем триплет{K[i]-1; 1; i} (левый конец) и триплет {K[i]+1; -1; i} (правый конец). Сортируем по первому полю, при равенстве раньше пойдёт пара с +1.

Создадим также массив пометок (boolean) и стек.

Пройдём по массиву по порядку. Если встретили левый конец, кладём его номер (третье поле) в стек.

Если встретили правый непомеченный конец, то: извлекаем из стека всё, что там есть, подсчитывая количество (M) и помечая соотв ячейки в массиве пометок. Добавляем к результату (M+1)/2 (получается целочисленное деление с округлением вверх).

А если правый помеченный - то ничего не делаем.

▲ 1

Я бы отсортировал просто диоптрии циклопов и покупал бы очки для соседей.

Пример на C#

int PairsCount(int[] data)
{
    // Сортирую
    Array.Sort(data);

    var ret = 0;
    int ind = 0;

    while (ind < data.Length)
    {
        if (ind == data.Length - 1)
        {
            ret++;
            break;
        }

        // проверяю соседей (ind и ind+1 индексы)
        // покупаю пару либо для одного, либо для двух циклопов
        if (data[ind + 1] - data[ind] <= 2)     
            ind += 2;       
        else        
            ind += 1;   

        ret++;
    }
    
    // конец
    return ret;
}

Проверка

Console.WriteLine(PairsCount(new[] { 1, -1, 2, 3, -3 }));

Вывод

3