Блог

Учитывая N элементов со значениями x[1], ..., x[n] и целым числом K, найдите алгоритм линейного времени для упорядочивания этих N элементов в K непустых группах таким образом, чтобы в каждой группе диапазон (разница между минимальными и максимальными значениями элемента / ключами в каждой группе) был минимизирован и, следовательно, сумма диапазонов была минимальной.

Например, учитывая N=4 , K=2 и элементы 1 1 4 3 , минимальный диапазон равен 1 для групп (1,1) и (4,3) .

Вы можете выполнить бинарный поиск ответа.
Предположим, что оптимальным ответом является x . Теперь вам следует проверить, можем ли мы сгруппировать элементы в k групп, где максимальная разница между элементами группы составляет не более x. Это можно сделать в O (n) [после сортировки массива]. Пройдите по отсортированному массиву и выбирайте последовательные элементы, пока разница между минимальным числом, выбранным вами для этой группы, и максимальным числом, выбранным вами, не превысит x. После этого вы должны инициализировать новую группу и повторить этот процесс. В конце подсчитайте, сколько групп вы создали. Если количество групп больше, чем k, мы можем заключить, что мы не можем сгруппировать элементы в k групп, где ответом является x. Итак, мы должны увеличить x. С помощью двоичного поиска по x мы можем найти минимум x.

Общая сложность составляет O (NlogN).

Вот пример реализации на C

 #include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int n = 4, k = 2;
    std::vector<int> v = {1, 1, 4, 3};
    sort(v.begin(), v.end());

    int low = 0, high = *max_element(v.begin(), v.end());

    while ( low < high ){
        int x = (low high)/2;

        int groups = 0;
        int left = 0;
        while (left < v.size()){
            int right = left;
            while( right < v.size() amp;amp; v[right] - v[left] <= x ){
                  right;
            }
              groups;
            left = right;
        }
        // printf("x:%d groups:%dn", x, groups );
        if (groups > k)
        {
            low = x   1;
        } else {
            high = x;
        }
    }

    cout << "result is " << low << endl;

}
  

Хорошо, я предположу, что мы хотим минимизировать сумму различий по всем группам.

1. Давайте отсортируем числа. Существует оптимальный ответ, в котором каждая группа представляет собой последовательный сегмент в отсортированном массиве (доказательство: пусть A1 < B1 < A2 < B2. Мы можем обменять A2 и B1. Ответ не увеличится).

2. Пусть a[l], a [l 1], …, a[r] является группой. Это стоит a[r] - a[l] = (a[r] - a[r - 1]) (a[r - 1] - a[r - 2]) ... (a[l 1] - a[l]) . Это приводит нас к ключевому пониманию: k группы — это k - 1 пробелы, а ответ — a[n - 1] - a[0] - sum of gaps . Таким образом, нам просто нужно максимизировать пробелы.

3. Вот окончательное решение:

   • отсортируйте массив
   • вычислите различия между соседними числами
   • возьмите k - 1 наибольшие различия. Именно здесь группы разделяются.
   • Мы можем найти k-1 -й по величине элемент за линейное время (или, если нас устраивает O(N log N) время, мы можем просто отсортировать их). Вот и все.

Вот пример:

x = [1, 1, 4, 3], k = 2
сортировка: [1, 1, 3, 4]
различия: [0, 2, 1]
с учетом k - 1 = 1 наибольших пробелов: это 2. Таким образом, группами являются [1, 1] и [3, 4] .

Немного более надуманный:
x = [8, 2, 0, 3], k = 3
сортировка: [0, 2, 3, 8]
различия: [2, 1, 5]
с учетом k - 1 = 2 наибольших пробелов: они равны 2 и 5. Таким образом, группы имеют [0], [2, 3], [8] общую стоимость 1.