【算法题】数组分段

清洁工：假设有m个房间，清洁每个房间耗时用一个数组表示，10、20、30、40、50、60、70、80、90，安排n个清洁工，将连续的房间分成n份，每部分耗时求和，其最大值为此种分法的总耗时。求最快的耗时是多少。例如3个清洁工的话，10 20 30 40 50 | 60 70 | 80 90，此时是最快的，耗时为170。

题目：给定一个数组，和一个值k，数组分成k段。要求这k段子段和最大值最小。求出这个值。

解析：

---

• 动态规划：

使用dp[n][k]表示前n个房间，k个清洁工的最优解

dp[n][k]=min⎧⎩⎨⎪⎪⎪⎪⎪⎪max(dp[0][k−1],∑ni=0A[i])max(dp[1][k−1],∑ni=1A[i])...max(dp[n][k−1],∑ni=nA[i])

---

• 二分查找：

此题可以想象成把数据按顺序装入桶中，m即是给定的桶数，问桶的容量至少应该为多少才能恰好把这些数装入k个桶中（按顺序装的）。

首先我们可以知道，桶的容量最少不会小于数组中的最大值，即桶容量的最小值（小于的话，这个数没法装进任何桶中），假设只需要一个桶，那么其容量应该是数组所有元素的和，即桶容量的最大值；其次，桶数量越多，需要的桶的容量就可以越少，即随着桶容量的增加，需要的桶的数量非递增的（二分查找就是利用这点）；我们要求的就是在给定的桶数量m的时候，找最小的桶容量就可以把所有的数依次装入k个桶中。在二分查找的过程中，对于当前的桶容量，我们可以计算出需要的最少桶数requiredPainters，如果需要的桶数量大于给定的桶数量k，说明桶容量太小了，只需在后面找对应的最小容量使需要的桶数恰好等于k；如果计算需要的桶数量小于等于k，说明桶容量可能大了（也可能正好是要找的最小桶容量），不管怎样，该桶容量之后的桶容量肯定不用考虑了（肯定大于最小桶容量），这样再次缩小查找的范围，继续循环直到终止，终止时，当前的桶容量既是最小的桶容量。

---

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace::std;
#define debug_

bool IsOk(vector<int>& vec,int k, long long tmp_max)
{
auto iter = max_element(vec.begin(), vec.end());
if (*iter>tmp_max)  return false;

int count(1);
long long tmp_sum(0);

for (auto i = 0; i < vec.size();++i)
    {
        tmp_sum += vec[i];
if (tmp_sum>tmp_max)
        {
            count++;
            tmp_sum = vec[i];
        }
    }
if (count>k)
return false;
else
return true;
}

int func(vector<int>& vec,int k)
{
if (vec.size()<k)
return -1;
long long left(0), right(0);
    right = accumulate(vec.begin(), vec.end(), 0);

long long mid = left + ((right - left) >> 1);

while (left+1<right)
    {
if (IsOk(vec,k,mid))
        {
            right = mid;
        }
else
        {
            left = mid;
        }
        mid = left + ((right - left) >> 1);
    }
return right;
}

int main()
{
vector<int> vec;
int k;
#ifdef debug_
//int a[] = { 1, 2, 3, 4 };
int a[] = {1,2,3,4,5,6,7,8,9,10,11};
    vec.insert(vec.begin(),a,a+11);
    k = 3;
#else
#endif
cout<<func(vec,k)<<endl;
return 0;
}

---