Я знаю, что мы можем использовать метод слияния и деления сортировки слиянием, чтобы найти инверсии. Но мне было интересно, как наиболее оптимально удалить подмассив, чтобы уменьшить количество инверсий. Нам нужно удалить подмассив размера K. И я знаю метод грубой силы, при котором я продолжаю удалять подмассивы размера k и продолжаю считать инверсии, но это занимает O(n^2) времени. Мне нужно что-то в O(nlogn) или O(n)
Как удалить подмассив размера K, чтобы минимизировать количество инверсий в массиве
Tyron Sequeria
9 августа 2021 в 06:04
62
0
Нам нужно удалить подмассив размера K. И я знаю метод грубой силы, при котором я продолжаю удалять подмассивы размера k и продолжаю считать инверсии, но это занимает O(n^2) времени. Мне нужно что-то в O(nlogn) или O(n)
Что вы пробовали? Где ты застрял? Пожалуйста, покажите минимальный воспроизводимый пример. Вы используете С++ или Python?
@Tyron Sequeria Извините, я пропустил
k sizeв названииПожалуйста, не добавляйте ненужные теги. Это не вопрос C++ и не вопрос Python.