Упорядочить п элементы по к непустым группам таким образом, что разность между минимальным элементом и максимальным элементом каждой группы минимизируются

Question

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

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

Answer 1

Вы можете бинарно найти ответ.
Предположим, что оптимальным является 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() && v[right] - v[left] <= x){ 
       ++right; 
      } 
      ++groups; 
      left = right; 
     } 
     // printf("x:%d groups:%d\n", x, groups); 
     if (groups > k) 
     { 
      low = x + 1; 
     } else { 
      high = x; 
     } 
    } 

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

} 

Answer 2

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

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. Вот окончательное решение:

   • сортировать массив
   • Compute различия между соседними числами
   • принимают 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.