Блог

в настоящее время я решаю проблему, которая гласит:

Компания подала заявление о банкротстве и решила заплатить сотрудникам последними оставшимися ценными предметами в компании, только если их можно распределить равномерно между ними, чтобы все они получили по крайней мере 1 предмет, и чтобы разница между сотрудником, несущим самые ценные предметы, и сотрудником, несущим наименее ценные предметы.не может превышать определенное значение x; Ввод:

• Первая строка содержит количество сотрудников;
• Вторая строка содержит значение x, так что разница между сотрудником, несущим наиболее ценные предметы, и сотрудником, несущим наименее ценные предметы, не может превышать;
• Третья строка содержит все элементы с их значением; Вывод:
• Первое число — это наименее ценная корзина товаров, а второе — самая ценная корзина;

Пример:

Ввод:
5
4
2 5 3 11 4 3 1 15 7 8 10

Вывод: 13 15

Ввод:
5
4
1 1 1 11 1 3 1 2 7 8

Вывод: НЕТ (невозможно распределить равномерно)

Ввод:
5
10
1 1 1 1

Вывод: НЕТ (невозможно распределить равномерно)

Мое решение для решения этой проблемы с первым вводом состоит в том, чтобы отсортировать элементы в порядке возрастания или убывания, начиная с
2 5 3 11 4 3 1 15 7 8 10 —> 1 2 3 3 4 5 7 8 10 11 15
затем создайте список смежности или просто сохраните его в простых переменных, гдемы добавляем наибольшее число в наименьшую корзину при повторении значений элементов
Элемент массива 0: 15
Элемент 1: 11 <- 3 (сумма 14)
Элемент 2: 10 <- 3 (сумма 13)
Элемент 3: 8 <- 4 <- 1 ( сумма 13)
Элемент 4: 7 <- 5 <- 2 (сумма 14)
Так что мое решение будет иметь O (nlogN 2n), первая часть с использованием сортировки слиянием, а затем нахождение максимального и минимального значения, что вы, ребята, думаете об этом решении?