Как удалить подмассив размера K, чтобы минимизировать количество инверсий в массиве

avatar
Tyron Sequeria
9 августа 2021 в 06:04
62
0
0

Я знаю, что мы можем использовать метод слияния и деления сортировки слиянием, чтобы найти инверсии. Но мне было интересно, как наиболее оптимально удалить подмассив, чтобы уменьшить количество инверсий. Нам нужно удалить подмассив размера K. И я знаю метод грубой силы, при котором я продолжаю удалять подмассивы размера k и продолжаю считать инверсии, но это занимает O(n^2) времени. Мне нужно что-то в O(nlogn) или O(n)

Источник
Tyron Sequeria
9 августа 2021 в 06:29
0

Нам нужно удалить подмассив размера K. И я знаю метод грубой силы, при котором я продолжаю удалять подмассивы размера k и продолжаю считать инверсии, но это занимает O(n^2) времени. Мне нужно что-то в O(nlogn) или O(n)

Alan Birtles
9 августа 2021 в 06:31
0

Что вы пробовали? Где ты застрял? Пожалуйста, покажите минимальный воспроизводимый пример. Вы используете С++ или Python?

MBo
9 августа 2021 в 06:35
0

@Tyron Sequeria Извините, я пропустил k size в названии

Evg
9 августа 2021 в 06:55
0

Пожалуйста, не добавляйте ненужные теги. Это не вопрос C++ и не вопрос Python.

Ответы (0)