Разделите массив на k непрерывных разделов так, чтобы сумма максимального раздела была минимальной

Это пример двоичного поиска в пробном пространстве.

int min_max_sum(std::vector<int> & a){int n=a.size();

long long high=0,low=0;
for (int i = 0; i < n; ++i)
{
high+=a[i];
low=max(a[i],low);
}

while(low<=high){
long long mid = (low+high)/2;

long long part_sum=0;
int parts=0;
for (int i = 0; i < n; ++i)
{
if (part_sum+a[i]>mid)
{
part_sum=0;
parts++;
}else{
part_sum+=a[i];
}
}
if (parts<k)
{
low=mid+1;
}else{ //if we have got exactly k parts or more, keep on decreasing the value of sum of subarray
high=mid-1;
}
}

return high;
}

сложность: O (n log (сумма (массив))).

Но поскольку логрифмы экспоненциально лучше линейных, эта сложность довольно хорошая.

сложность наихудшего случая: O (n log (INT_MAX * n)) = O (32 n + n log (n)) = O (n log (n)).

Начнем с примера. Предположим, N = 5 и К= 3 (при условии, что после деления будет три части). Пусть наш массив будет {1,2,8,4,9}. Мы можем наблюдать, что если К был равен 1, тогда сумма максимального разбиения была бы суммой (все элементы массива), т.е. 24, и если К= 5, тогда сумма максимального разбиения будет равна max (все элементы массива), т.е. 9. Теперь мы можем наблюдать, что с увеличением k сумма минимального значения максимального разбиения уменьшается. Наш алгоритм при этом использует бинарный поиск. Но как это сделать????? Посмотрев на вопрос — мы можем видеть, мы должны найти минимум максимума, который вызывает чувство проблем, таких как — «FFFFTTTTTTTT», где мы должны найти первый T. Мы собираемся сделать то же самое, но возьмем помощь функции в этом. (Посмотрите на код и ответьте отсюда, параллельно). Вспомогательная функция найдет значение K, когда будет предоставлена ​​минимальная сумма максимального раздела. Мы инициализируем low = max (все элементы массива), здесь low = 9 и high = sum (все элементы массива), т. е. high = 24. Поэтому mid = 16, поэтому для min_max_dist = 16 наша вспомогательная функция вернет требуемое количество k.Если число к>К,это означает, что наш min_max_dist может вместить в себя больше значений. Итак, мы будем увеличивать наше низкое значение до середины + 1, и если число k<знак равноК, это означает, что за меньшее количество разделов мы можем достичь этого min_max_dist ,, но мы можем сделать больше разделов, и, следовательно, мы можем уменьшить высокое значение до середины. Итак, наш код будет выполняться на нашем примере следующим образом: —

    low           high               mid       number_of_k
9             24                 16         9
9             16                 12         2
9             12                 10         4
11            12                 11         3

и наконец наш результат-> low = 11 будет возвращен ..

    #include <bits/stdc++.h>
#define ll long long int
using namespace std;

ll number_of_k(ll arr[],ll n,ll minimum_max__dist){
ll sum=0;
ll k=1;
for(ll i=0;i<n;i++){
sum+=arr[i];
if(sum > minimum_max__dist){
sum=arr[i];
k++;
}
}
return k;
}

ll Max(ll arr[], ll n)
{
ll max1 = -1;
for (ll i = 0; i < n; i++)
if (arr[i] > max1)
max1 = arr[i];
return max1;
}

ll Sum(ll arr[], ll n)
{
ll sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}

ll min_max_bin_search(ll arr[],ll n,ll k){
ll low=Max(arr,n);
ll high=Sum(arr,n);
ll mid;
while(low<high){
mid=low+(high-low)/2;
if(number_of_k(arr,n,mid)<=k)
high=mid;
else
low=mid+1;
}
return low;
}int main()
{
ll n,k;
cin>>n>>k;
ll arr[n];
for(ll i=0;i<n;i++)cin>>arr[i];
cout<<min_max_bin_search(arr,n,k)<<endl;

return 0;
}

Временная сложность этого алгоритма is-> O (nlogn)

Прочитайте эту статью о бинарном поиске-> https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/
а также
Решить эту проблему-> http://www.spoj.com/problems/AGGRCOW/

Вы можете найти хорошее описание решения на основе динамического программирования здесь: https://www.geeksforgeeks.org/painters-partition-problem/ а также
Это сложность O (k * N ^ 2).

Чтобы получить лучшее решение, вы можете использовать метод двоичного поиска, предложенный другими. Вы можете найти более подробное решение, которое использует бинарный поиск здесь: https://www.geeksforgeeks.org/painters-partition-problem-set-2/ и это сложность O (NlogN)

Это может быть решено с помощью динамическое программирование:

Давайте сначала определимся DP[n,m] быть оптимальным решением для деления подмассива C[1..n] в m частей. Где каждая часть имеет хотя бы один элемент.

DP[n,1] = sum(C1:Cn)
DP[n,n] = max(C1:Cn)
DP[n,m] = min( sum(Ck:Cn) + DP[k-1,m-1] )
where k goes from m to n

Объяснение:
DP[n,1] — Базовый случай, когда количество разделов 1 есть только один путь — все элементы остались (от 1 до n).
DP[n,n] — Всякий раз, когда количество разделов равно количеству элементов, оставленных в массиве, существует только один допустимый способ его разделения — каждый элемент в отдельном разделе, поэтому раздел с максимальной суммой является максимальным элементом в массиве.
DP[n,m] — Это главное решение. Мы не знаем точно, сколько элементов будет нашим следующим разделом, поэтому нам нужно пройтись по всем параметрам и получить от них минимум.

Разделение — это просто проблема грубой силы. Вы должны сосредоточиться на функции, чтобы минимизировать. Так что вы должны минимизировать отклонение от среднего.

int sum_arr(int *arr,int size)
{
int res=0;
while (size-->0)
res+=*arr++;
return res;
}
int   minimize( const int *array, int size)
{
int i,j,cur_i;
double dev, cur_min,avg=(double)sum_arr(array,size)/size;

for (i=1;i<size-1;i++)
{
dev=abs(avg-sum_arr(array,i));
dev+=abs(avg-sum_arr(array+i,size-i);
if (dev<cur_min)
{
cur_min=dev;
cur_i=i;
}
}
return cur_i;
}

Простой код будет: (не проверено)