Задача на жадный алгоритм

Question

Задача заключается в том, что нужно рассадить учеников в классе. За каждой партой сидят два школьника. Для каждой парты известен ее уровень «контролируемости», а для каждого ученика – его уровень «послушания». Для улучшения дисциплины нужно посадить учеников, чтобы за каждой партой сидели два школьника:

1)Послушание одного из школьников строго меньше контролируемости этой парты

2)Послушание другого строго больше.

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

Answer 1

Получилось что то типа псевдокода на сишарпе

Идея: отсортировать учеников по послушаемости и разбить пополам - то есть для любого ученика из верхней группы вся нижняя группа имеет меньшее послушание. Соотверственно, для любой парты, один ученик будет из одной группы, второй - из другой группы. Потом отсортировать парты по контролируемости и заполнить их.

void Main()
{
    var students = new int[] { 1, 2, 3, 4, 4, 6, 7, 8, 9, 19, 4, 5 };
    var desks = new int[] { 4, 5, 6, 7, 8, 30};

    Array.Sort(students);
    Array.Sort(desks);

    int low = 0;
    int high = students.Length  / 2;
    int desk = 0;
    
    int good = 0;

    while (low < students.Length / 2 && high < students.Length && desk < desks.Length)
    {
        var d = desks[desk];
        var l = students[low];
        var h = students[high];

        if (l >= d)
        {
            desk++;
            continue;
        }

        if (h <= d)
        {
            high++;
            continue;
        }

        Console.WriteLine($"We are putting low:{l} and high {h} on desk {d}");
        low++;
        high++;
        desk++;
        good++;
    }

    Console.WriteLine($"Good desks {good}, bad desks {desks.Length - good}");
}

Результат

We are putting low:1 and high 5 on desk 4
We are putting low:2 and high 6 on desk 5
We are putting low:3 and high 7 on desk 6
We are putting low:4 and high 8 on desk 7
We are putting low:4 and high 9 on desk 8
Good desks 5, bad desks 1

БЛОГ НА HUSL

Задача на жадный алгоритм

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