За один ход увеличить или уменьшить любой элемент массива на 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, ваша правда, быстрый поиск по ключу реализуется через словарь.
Не совсем элементарно, но я встречал такие реализации

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

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

	За один ход увеличить или уменьшить любой элемент массива на 1, всего таких операций можно сделать не больше K 11.01.2025, 17:09. Показов 7189. Ответов 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,820
	21.01.2025, 01:21
	Надо получить вставку ценой O(log N). 0

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

@Mikhaylo 820 / 579 / 75 Регистрация: 20.09.2014 Сообщений: 3,820
	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