分组

分组

描述

有 n 个正整数排成一排，你要将这些数分成m 份（同一份中的数字都是连续的，不能隔开），同时数字之和最大的那一份的数字之和尽量小。

输入

输入的第一行包含两个正整数 n，m。接下来一行包含n 个正整数。

输

输出一个数，表示最优方案中，数字之和最大的那一份的数字之和。

样例 1 输入

样例 1 输

样例 1 解释

若分成 2 和 1、2、2、3，则最大的那一份是 1+2+2+3=8； 若分成 2、1 和 2、2、3，则最大的那一份是 2+2+3=7；

若分成 2、1、2 和 2、3，则最大的那一份是 2+1+2 或者是 2+3，都是 5； 若分成 2、1、2、2 和 3，则最大的那一份是 2+1+2+2=7。

所以最优方案是第三种，答案为 5。

样例 2

请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。

限制

对于 50%的数据，n ≤ 100，给出的 n 个正整数不超过 10；

对于 100%的数据，m ≤ n ≤ 300000，给出的 n 个正整数不超过 1000000。时间：4 sec

空间：512 MB

提示

[大家记得看到“最大的最小”这一类语言，一定要想二分能不能做。]

[我们二分最大的那一份的和 d，然后从左向右分组，在一组中，在和不超过d 的情况下尽量往右分。若最终分出来的组数小于等于m，则这显然是合法的（我们在分出来的组里随便找个地方切开，总能变到m 组，且每组的和不超过 d）]

[这个 d 显然是单调的，即，若和不超过d 能分成m 组，则和不超过 d+1 也是能分成m 组的，故二分正确。]

代码

#include<iostream> #include<vector>

#pragma warning(disable:4996) using namespace std;

typedef long long ll;

bool check(ll mid, ll n, ll m,vector<int> &a)

{

ll sum = 0;

int cut = 1;

for (int i = 0; i < n; ++i)

{

if (a[i] > mid)

return false;

sum += a[i];

if (sum > mid)

{

sum = a[i];

cut += 1;

}

}

return cut <= m;

}

ll GetAnswer(ll n, ll m, vector<int> &a)

{

ll l = 1, r = 0;

for (int i = 0; i < n; ++i)

{

r += a[i];

}

while (l <= r)

{

ll mid = (l + r) / 2;

if (check(mid, n, m, a))

r = mid - 1;

else

l = mid + 1;

}

return r + 1;

}

int main()

{

ll n, m;

cin >> n >> m;

vector<int> a;

for (ll i = 0; i < n; ++i)

{

int temp;

scanf("%d", &temp);

a.emplace_back(temp);

}

ll result = GetAnswer(n, m, a);

cout << result << endl;

return 0;

}