Минимизация корректировок расписания

Question

Чтобы набрать форму к лету, Виктория решила бегать каждый день. До лета осталось всего n дней — именно на протяжении этого срока она и будет бегать. Ее личный тренер уже составил ей расписание: в i-й день Виктория должна пробежать ai километров.

Виктория считает i-й (3<=i<=n) день хорошим, если в этот день она пробежит не меньше, чем в первый день, и не больше, чем во второй день. Расписание же ей понравится, если хотя бы m дней будут хорошими. В расписании можно делать корректировки: произвольное ai (1<=i<=n) можно увеличить или уменьшить на 1 километр. Разрешается корректировать один и тот же день несколько раз.

Какое минимальное корректировок необходимо внести в расписание, чтобы оно понравилось Виктории?

Формат входных данных

Первая строка содержит числа n (3<=n<=2*10^5) и m (1<=m<=n-2) — количество дней до лета и количество хороших дней, которое необходимо Виктории, чтобы ей понравилось расписание.

Следующая строка содержит числа a1, a2, ... , an (1<=ai<=10^9), где ai— количество километров, которое должна пробежать Виктория согласно начальному расписанию.

Формат выходных данных

Выведите одно число — минимальное количество корректировок, которое необходимо внести в расписание, чтобы оно понравилось Виктории.

Комментарий к примеру

В примере можно дважды уменьшить a3 на единицу, чтобы расписание понравилось Виктории.

Примеры данных

ввод:

3 1

3 4 6

Вывод:

2

Answer 1

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

Условия:

Для того чтобы день был хорошим (для i >= 3), количество километров в день i должно быть между количеством километров в первый и второй дни, то есть: $a_1 \leq a_i \leq a_2$
Необходимо, чтобы хотя бы m дней были хорошими.

Пошаговый план:

Прочитаем входные данные. Входные данные содержат:
- n (количество дней),
- m (необходимое количество хороших дней),
- a (массив километров).
Определим корректировки для каждого дня. Для каждого дня (i начиная с 3) нужно посчитать, сколько корректировок требуется, чтобы километры на этом дне попали в интервал от a1 до a2. То есть:
- Если $a[i] < a1$ , нужно увеличить значение $a[i]$ до $a1$ .
- Если $a[i] > a2$ , нужно уменьшить значение $a[i]$ до $a2$ .
- Если $a[i]$ уже в пределах от $a1$ до $a2$ , корректировки не нужны.
Таким образом, для каждого дня i (начиная с 3) можно посчитать необходимое количество корректировок.
Отсортируем корректировки по возрастанию. Так как нам нужно минимизировать количество корректировок, мы должны выбрать те дни, где корректировки минимальны. После того как мы получим все корректировки, отсортируем их и выберем m самых маленьких, чтобы удовлетворить условию "хотя бы m хороших дней".
Вычислим минимальное количество корректировок.

Алгоритм:

Прочитаем входные данные.
Посчитаем количество корректировок для каждого дня (i от 3 до n).
Отсортируем эти корректировки.
Возьмем сумму m минимальных корректировок.
Выведем результат.

Реализация:

python
def solve():
    # Чтение входных данных
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    
    a1 = a[0]
    a2 = a[1]
    
    # Массив для хранения корректировок для каждого дня
    corrections = []
    
    # Для каждого дня i (с 3-го по n-й), посчитаем сколько нужно корректировок
    for i in range(2, n):
        if a[i] < a1:
            corrections.append(a1 - a[i])  # Нужно увеличить до a1
        elif a[i] > a2:
            corrections.append(a[i] - a2)  # Нужно уменьшить до a2
        else:
            corrections.append(0)  # Уже в пределах [a1, a2]
    
    # Сортируем корректировки по возрастанию
    corrections.sort()
    
    # Чтобы расписание понравилось Виктории, нужно m хороших дней,
    # поэтому берем m минимальных корректировок
    result = sum(corrections[:m])
    
    # Выводим результат
    print(result)

Пояснение:

Чтение входных данных: Мы считываем значения n, m и массив a из входных данных.
Расчет корректировок: Для каждого дня начиная с 3-го (индекс 2) мы проверяем, сколько корректировок нужно, чтобы соблюсти условие $a_1 \leq a_i \leq a_2$ .
Сортировка корректировок: Мы сортируем массив корректировок и выбираем минимальные m значений. Это те дни, где нужно наименьше корректировать километры, чтобы они стали хорошими.
Вывод результата: Мы выводим сумму первых m минимальных корректировок, которая и будет минимальным количеством изменений.

Пример:

Ввод:

text
3 1
3 4 6

Объяснение:

a1 = 3, a2 = 4.
День 3 (i=3): 6 километров. Нужно уменьшить до 4, т.е. 6 - 4 = 2 корректировки.
Нужно хотя бы 1 хороший день. Мы можем сделать день 3 хорошим за 2 корректировки.

Вывод:

Время работы:

Мы проходим по всем дням от 3 до n (всего n-2 дней), вычисляем для каждого количество корректировок — это O(n).
Сортировка корректировок занимает O(n log n).
В общем, время работы алгоритма — O(n log n), что подходит для n до 200,000.

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

Answer 2

Результаты:

Точность модели: 57.14% (0.5714)
Количество листьев, классифицирующих день как рабочий день: 5

Теперь модель построена корректно, и дерево решений визуализировано. Если нужно попробовать другие значения max_depth, можно повторить эксперименты с изменением этого параметра.

Минимизация корректировок расписания

Question

Какое минимальное корректировок необходимо внести в расписание, чтобы оно понравилось Виктории?

Формат входных данных

Первая строка содержит числа n (3<=n<=2*10^5) и m (1<=m<=n-2) — количество дней до лета и количество хороших дней, которое необходимо Виктории, чтобы ей понравилось расписание.

Следующая строка содержит числа a1, a2, ... , an (1<=ai<=10^9), где ai— количество километров, которое должна пробежать Виктория согласно начальному расписанию.

Формат выходных данных

Выведите одно число — минимальное количество корректировок, которое необходимо внести в расписание, чтобы оно понравилось Виктории.

Комментарий к примеру

В примере можно дважды уменьшить a3 на единицу, чтобы расписание понравилось Виктории.

Примеры данных

ввод:

3 1

3 4 6

Вывод:

2

Réponse

Условия:

Пошаговый план:

Алгоритм:

Реализация:

Пояснение:

Пример:

Время работы:

Question

Python

Python

Python

Python

Python

Python

Réponse

Partager cette Q&R