Разделите массив на k непрерывных разделов так, чтобы сумма максимального раздела была минимальной
Здесь подмножество максимальной суммы является одним из k подмножеств, которые дают максимальную сумму, например: arr = [10,5,3,7] и k = 2 возможных способа разделить arr на k подмножеств: {10, [5,3,7]}, {[10,5], [3,7}, {[10,5,3], 7} и {[10,5], [3,7} - оптимальный вариант. Изменить: это эквивалент https://www.codechef.com/DI15R080/problems/MINMAXTF
7 ответов
Предположим, вы знаете, что ответ равен x, что означает, что сумма максимального подмножества равна x. Вы можете проверить это предположение с помощью жадного алгоритма O (n). (Обходите массив слева направо и выбирайте элементы, пока сумма этого подмножества не станет меньше x). Теперь вы можете выполнить бинарный поиск по x и найти минимальное значение для x. Сложность этого алгоритма O (nlogn).
Это пример двоичного поиска в пробном пространстве.
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 и k= 3 (при условии, что после деления будет три части). Пусть наш массив будет {1,2,8,4,9}. Мы можем заметить, что если бы k было равно 1, то сумма максимального разбиения была бы суммой (все элементы массива), т. Е. 24, а если k= 5, то сумма максимального разбиения была бы max(все элементы массива), то есть 9. Теперь мы можем наблюдать, что с увеличением k сумма минимального значения максимального разбиения уменьшается. Наш алгоритм при этом использует бинарный поиск. Но как это сделать????? Посмотрев на вопрос - мы можем видеть, мы должны найти минимум максимума, который вызывает чувство проблем, таких как - "FFFFTTTTTTTT", где мы должны найти первый T. Мы собираемся сделать то же самое, но возьмем помощь функции в этом.(Посмотрите на код и ответьте отсюда, параллельно). Вспомогательная функция найдет значение K, когда будет предоставлена минимальная сумма максимального раздела. Мы инициализируем low=max(все элементы массива), здесь low=9 и high=sum(все элементы массива), т. е. high=24. Поэтому mid=16, поэтому для min_max_dist=16 наша вспомогательная функция вернет требуемое количество k.Если число k>K, это означает, что наш min_max_dist может вместить больше значений. Таким образом, мы будем увеличивать наше низкое значение до середины +1, и если число k<= 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;
}
Простой код будет:(не проверено)
// This code works only if you have to find in a contiguous segment
bool isPossible(vector<int>& nums, int mid, int k) {
int n = nums.size(), Count = 1, Sum = 0;
for(int i = 0; i < n; i++) {
if(nums[i] > mid) return false;
Sum += nums[i];
if(Sum > mid) {
Count++;
Sum = nums[i]
}
}
return Count <= k;
}
int Func(vector<int>& nums, int k) {
int n = nums.size();
int low = 0, high = accumulate(nums.begin(), nums.end(), 0);
while(low <= high) {
int mid = (low + high) / 2;
if(isPossible(nums, mid, k)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return ans;
}