За один ход увеличить или уменьшить любой элемент массива на 1, всего таких операций можно сделать не больше K

@i_have_question · Регистрация: 11.01.2025

Студворк — интернет-сервис помощи студентам

Дан список A из N чисел, а также число K. Можно за один ход увеличить или уменьшить любой элемент массива на 1, всего таких операций можно сделать не больше K раз.
Какая макс. длина может быть у какого-то подотрезка, в которым все элементы одинаковые?

В первой строке два числа - N и K. Во второй строке N чисел, i-тый элемент равен A[i].

Ограничения:
1 ≤ N ≤ 100 000
0 ≤ K ≤ 1 000 000 000
0 ≤ A[i] ≤ 100 000 000

Ввод:
11 7
3 5 8 9 2 7 6 5 3 9 7

Вывод:
4

Объяснение:
Можно выбрать отрезок 2-7-6-5. Выполним операцию 4 раза на первом элементе, тогда получаем 6-7-6-5. Выполним операцию 1 раз на втором элементе, итого 5 операции, получаем 6-6-6-5. Выполним операцию на последнем элементе, итого 6 операции, получаем 6-6-6-6. Все элементы одинаковы, значит размер отрезка (4) подходит. Можно показать, что больше такого отрезка, с длиной больше 4, нет.

@Igor3D · 20.01.2025, 22:58

Сообщение от Mikhaylo

[3, 5, 6, 7, 8, 9]
Вот же они по середине. Индекс первой медианы 6/2-1 = 2, индекс второй медианы 6/2 = 3 (индексы начинаются с нуля).

Или держать данные сортированными или быстрый доступ по индексу, технически нельзя иметь и то и другое, во всяком случае стандартными средствами. Поэтому Shamil1 написал свое дерево чтобы получать индексы за O(log). За обсуждением следите

@Shamil1 · 21.01.2025, 00:24

Я пробовал получать медиану за О(1). Но с ним программа работает в 4 раза медленнее, так как сам SortedSet медленный.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Window
{
    private SortedSet<(int, int)> Left = new SortedSet<(int, int)>();
    private SortedSet<(int, int)> Right = new SortedSet<(int, int)>();
    
    public int Low => Left.Max.Item1;
    public int High => Right.Min.Item1;
    
    public int Width => Left.Count + Right.Count;
    
    public void Add((int,int) item)
    {
        if (item.CompareTo(Left.Max) < 0)
        {
            Left.Add(item);
            BalanceLeft();
        }
        else
        {
            Right.Add(item);
            BalanceRight();
        }
    }
    
    public void Remove((int,int) item)
    {
        if (item.CompareTo(Left.Max) <= 0)
        {
            Left.Remove(item);
            BalanceRight();
        }
        else
        {
            Right.Remove(item);
            BalanceLeft();
        }
    }
    
    private void BalanceLeft()
    {
        if (Left.Count - Right.Count > 1)
        {
            var x = Left.Max;
            Left.Remove(x);
            Right.Add(x);
        }
    }
    
    private void BalanceRight()
    {
        if (Right.Count > Left.Count)
        {
            var x = Right.Min;
            Right.Remove(x);
            Left.Add(x);
        }
    }
}

@Mikhaylo · 21.01.2025, 01:21

Надо получить вставку ценой O(log N).

@Shamil1 · 21.01.2025, 10:49

Сообщение от Mikhaylo

Надо получить вставку ценой O(log N).

С использованием дерева все манипуляции с окном - вставка, удаление, поиск медианы - стоят O(log N).
С использованием двух SortedSet вставка и удаление стоят O(log N), но коэффициент хуже. Поиск медианы стоит O(1).

Насколько я понимаю, дешевле нельзя даже в теории. Вопрос только в уменьшении коэффициента

@Igor3D · 21.01.2025, 16:15

Сообщение от Shamil1

В C# в SortedSet у итератора есть только MoveNext.

Безобразие

Сообщение от Shamil1

С использованием двух SortedSet

Тогда надо "балансировать 2 дерева" что увеличивает расходы на вставку/удаление

Сообщение от Shamil1

Насколько я понимаю, дешевле нельзя даже в теории.

Ну почему, отслеживать счетчики нодов дерева не так уж и накладно. Просто в стандартном наборе этого нет, во всяком случае мне неизвестно

@Shamil1 · 21.01.2025, 18:02

Сообщение от Igor3D

Тогда надо "балансировать 2 дерева" что увеличивает расходы на вставку/удаление

Да. Вместо одной вставки/удаления в среднем два получается (в половине случаев нужно перенести из одной в другую для балансировки).

Сообщение от Igor3D

Ну почему, отслеживать счетчики нодов дерева не так уж и накладно.

Я про логарифм.

@Mikhaylo · 21.01.2025, 18:47

Ответ ИИ:

Для решения этой задачи можно использовать метод двух указателей в сочетании с жадным подходом. Вот алгоритм решения:
1. Инициализируем два указателя: left = 0 и right = 0.
2. Проходим по массиву, двигая правый указатель (right) вправо.
3. Для каждого подотрезка [left, right] считаем, сколько операций нужно, чтобы сделать все элементы равными медиане этого подотрезка.
4. Если количество необходимых операций не превышает K, обновляем максимальную длину.
5. Если количество операций превышает K, двигаем левый указатель (left) вправо, пока количество операций не станет меньше или равно K.
6. Повторяем шаги 3-5, пока правый указатель не дойдет до конца массива.

Вот реализация этого алгоритма на Python:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def max_equal_subarray_length(n, k, arr):
    arr.sort()
    left = 0
    max_length = 0
    total_operations = 0
 
    for right in range(n):
        total_operations += abs(arr[right] - arr[(left + right) // 2])
 
        while total_operations > k:
            total_operations -= abs(arr[left] - arr[(left + right) // 2])
            left += 1
 
        max_length = max(max_length, right - left + 1)
 
    return max_length
 
# Чтение входных данных
n, k = map(int, input().split())
arr = list(map(int, input().split()))
 
# Вывод результата
print(max_equal_subarray_length(n, k, arr))

Этот алгоритм работает за O(n log n) из-за сортировки массива. Сортировка нужна для того, чтобы эффективно находить медиану подотрезка.
Давайте разберем, как этот алгоритм работает на данном примере:
1. Сначала сортируем массив: [2, 3, 3, 5, 5, 6, 7, 7, 8, 9, 9]
2. Начинаем с left = 0 и right = 0.
3. Двигаем right вправо, считая необходимые операции.
4. Когда количество операций превысит K (7), начинаем двигать left вправо.
5. Продолжаем этот процесс до конца массива.

В итоге алгоритм найдет максимальный подотрезок длины 4, который можно сделать одинаковым за не более чем 7 операций.
Этот алгоритм эффективно решает задачу в рамках заданных ограничений.

@Shamil1 · 21.01.2025, 20:23

Сообщение от Mikhaylo

Этот алгоритм работает за O(n log n) из-за сортировки массива.

ИИ повеселил. Нужно найти подотрезок массива. Очевидно, после сортировки этого сделать нельзя.

@Igor3D · 21.01.2025, 20:34

Сообщение от Shamil1

ИИ повеселил.

Ну не только. Обратите внимание

Сообщение от Mikhaylo

Давайте разберем

Не знаю кто это: ИИ или его позвавший. Но в любом случае - безмятежная уверенность в правоте и готовность поучать

@Igor3D · 22.01.2025, 18:54

И, для полноты картины, типичный минус таких алгоритмов: "не параллелится"

@Mikhaylo · 23.01.2025, 06:52

Почему не параллелится? Бери left=right=0 для одного ядра и left=right=n/2 для другого.

@Shamil1 · 23.01.2025, 14:28

Сообщение от Mikhaylo

Почему не параллелится? Бери left=right=0 для одного ядра и left=right=n/2 для другого.

В теории - да. А на практике в данном конкретном случае выгоды не будет. Размер массива 100 тыс, а размер ответа 80 тыс. Поэтому, начав в самой первой части всё равно придётся идти до самой последней.

@Red white socks · 27.01.2025, 09:05

Сообщение от Shamil1

ИИ повеселил. Нужно найти подотрезок массива. Очевидно, после сортировки этого сделать нельзя.

Но так то он дал рабочую идею. Нужно только вместо сортировки организовать пересчет медианы при изменении окна за логарифм. Это реализуется с помощью 2 куч почти одинакового размера (размеры отличаются не более чем на 1).

@Shamil1 · 27.01.2025, 16:07

Сообщение от Red white socks

Но так то он дал рабочую идею.

Если брать первую часть описания (до кода), то да. Именно такой подход используется во всех решениях, приведённых в данной теме.

Сообщение от Red white socks

Это реализуется с помощью 2 куч почти одинакового размера

В стандартной куче (Binary Heap) нет возможности удалить (и даже найти) произвольный элемент за логарифм.
Я использовал SortedSet (C# код в #62), но работает в 4 раза медленней (что ожидаемо). По количеству операций у такого подхода преимуществ нет, а коэффициент хуже, так как используется более сложная структура данных.

@Red white socks · 29.01.2025, 08:38

Shamil1, да, не осилил всю тему целиком (только первая и последняя страница) и не видел решений с деревьями. Что касается стандартных реализаций кучи, то здесь да, удивляет, что сложилась практика не выносить поиск по ключу и изменение ключа в расшаренные методы, хотя private функциями в библиотеке все вроде разрулено.

@Shamil1 · 29.01.2025, 15:05

Сообщение от Red white socks

хотя private функциями в библиотеке все вроде разрулено

Есть пример?

Стандартная куча реализована в виде массива с операциями "поднять" и "опустить". Чтобы прикрутить к ней возможность удаления (поиска) произвольного элемента за логарифм, нужно в хэш-таблице хранить индексы всех элементов и обновлять их при каждой операции. Сомневаюсь, что такое есть в стандартной реализации.

@Igor3D · 31.01.2025, 19:04

Сообщение от Red white socks

Но так то он дал рабочую идею.

Да, изложение очень разумно, но "и только", задачу ИИ не понял. Как это часто бывает, богатырская сила охотно демонстрируется на простых/очевидных вещах, а про "мелочи" что 95% работы - молчок

Сообщение от Shamil1

Стандартная куча реализована в виде массива с операциями "поднять" и "опустить". Чтобы прикрутить к ней возможность удаления (поиска) произвольного элемента за логарифм, нужно в хэш-таблице хранить индексы всех элементов и обновлять их при каждой операции. Сомневаюсь, что такое есть в стандартной реализации.

"Произвольный элемент" - это обращение по индексу (в плюсах для этого идиотский термин "random access iterator"). Неплохая идея своего/кастомного контейнера типа дерево (смысла в "куче" не видно). Напрашивается взять исходники стандартного и добавить. Хотя, вероятно, это уже есть где-нибудь в boost (там лазить такой гемор)

@Red white socks · 01.02.2025, 23:09

Shamil1, ваша правда, быстрый поиск по ключу реализуется через словарь.
Не совсем элементарно, но я встречал такие реализации

Новые блоги и статьи Все статьи Все блоги /
Расчёт периметра прямоугольника по координатам вершин Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Вычислить периметр прямоугольника, заданного координатами своих вершин на плоскости. Решение: Создан документ со следующими. . .	Подсчёт частоты трёхбуквенных слов в тексте Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Выясните, сколько раз в предложенном тексте встречается каждое трехбуквенное слово. Решение: Создан документ с единственным. . .	Сумма и количество положительных элементов в чётных строках массива Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Вычислить сумму и количество положительных элементов массива, расположенных в четных строках. Решение: Создан документ с. . .	Поиск произведения положительных чётных чисел в последовательности Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Дана произвольная последовательность целых чисел. Найти произведение положительных четных чисел данной последовательности. . . .
Обработка трёх чисел: утроение и возведение в степень Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Даны три действительных числа. Утроить те из них, значения которых неотрицательны, и возвести в четвертую степень отрицательные. . . .	Расчёт стоимости яблок по весу Maks 18.07.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Написать программу вычисления стоимости некоторого количества (по весу) яблок. Решение: Создан документ, с табличной частью. . .	сукцессия 30. Фосфорный и азотный замки по "честному" закону лимитирования Либиха anaschu 16.07.2026 Основные достижения за последние дни 1. Механизм отложенного высвобождения фосфора Добавлен специальный пул для медленного разложения меланизированных гиф ЕСМ Реализована разная скорость. . .	Запрет пометки на удаление и отмены проведения Maks 16.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "ПутевойЛист" разработанного в КА2. Задача: запретить помечать на удаление и отменять проведения путевого листа при условии, если он сдан. . .

@i_have_question 0 / 0 / 0 Регистрация: 11.01.2025 Сообщений: 4

	За один ход увеличить или уменьшить любой элемент массива на 1, всего таких операций можно сделать не больше K 11.01.2025, 17:09. Показов 7070. Ответов 77 Метки нет (Все метки) Дан список A из N чисел, а также число K. Можно за один ход увеличить или уменьшить любой элемент массива на 1, всего таких операций можно сделать не больше K раз. Какая макс. длина может быть у какого-то подотрезка, в которым все элементы одинаковые? В первой строке два числа - N и K. Во второй строке N чисел, i-тый элемент равен A[i]. Ограничения: 1 ≤ N ≤ 100 000 0 ≤ K ≤ 1 000 000 000 0 ≤ A[i] ≤ 100 000 000 Ввод: 11 7 3 5 8 9 2 7 6 5 3 9 7 Вывод: 4 Объяснение: Можно выбрать отрезок 2-7-6-5. Выполним операцию 4 раза на первом элементе, тогда получаем 6-7-6-5. Выполним операцию 1 раз на втором элементе, итого 5 операции, получаем 6-6-6-5. Выполним операцию на последнем элементе, итого 6 операции, получаем 6-6-6-6. Все элементы одинаковы, значит размер отрезка (4) подходит. Можно показать, что больше такого отрезка, с длиной больше 4, нет. 0

@Mikhaylo 820 / 579 / 75 Регистрация: 20.09.2014 Сообщений: 3,814
	21.01.2025, 01:21
	Надо получить вставку ценой O(log N). 0

@Igor3D 1977 / 833 / 115 Регистрация: 01.10.2012 Сообщений: 5,117 Записей в блоге: 2
	22.01.2025, 18:54
	И, для полноты картины, типичный минус таких алгоритмов: "не параллелится" 0

@Mikhaylo 820 / 579 / 75 Регистрация: 20.09.2014 Сообщений: 3,814
	23.01.2025, 06:52
	Почему не параллелится? Бери left=right=0 для одного ядра и left=right=n/2 для другого. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	29.01.2025, 08:38
	Shamil1, да, не осилил всю тему целиком (только первая и последняя страница) и не видел решений с деревьями. Что касается стандартных реализаций кучи, то здесь да, удивляет, что сложилась практика не выносить поиск по ключу и изменение ключа в расшаренные методы, хотя private функциями в библиотеке все вроде разрулено. 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	01.02.2025, 23:09
	Shamil1, ваша правда, быстрый поиск по ключу реализуется через словарь. Не совсем элементарно, но я встречал такие реализации 0