思路:利用二分找到某个时间是满足“k个人可以完成” ,并且时间最小。
因为尽量让后面的人做任务,所以从后往前排任务(倒着分配)。从后往前遍历任务,如果此人加上这个任务超出之前求得的时间,就移到上一个人。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 10;
int t, k;
int ti[N];
bool check(int u)
{ // u秒可不可以由k个人完成
int s = 1; // 记录当前的人
int a[N]; // 记录每人任务时间
memset(a, 0, sizeof(a));
for (int i = 1; i <= t; i++) // 遍历t个任务
{
if (a[s] + ti[i] > u) // 如果当前时间加上当前任务的时间大于u
{
s++; // 选下一个人
a[s] += ti[i];
}
else
a[s] += ti[i];
}
if (s > k)
{ // 人数>k
return false;
}
return true;
}
int c[N][2]; //[每人][起点+终点]
void print(int u)
{ // u为时间
// 倒着分配
int i = k, temp = 0;
for (int j = t; j > 0; j--)
{
if (c[i][1] == 0)
{ // 结束
c[i][1] = j;
}
if (temp + ti[j] > u) // 时间超出,则换人(从后往前i--)
{
c[i][0] = j + 1;
i--;
temp = ti[j];
c[i][1] = j; // 结束
}
else
{ // 时间未超出
temp += ti[j];
}
}
c[i][0] = 1;
for (int i = 1; i <= k; i++)
{
if (c[i][0] == 0)
cout << 0 << " " << 0 << endl;
else
cout << c[i][0] << " " << c[i][1] << endl;
}
}
signed main()
{
int l = -1, r = 0, ans = 0;
cin >> t >> k;
for (int i = 1; i <= t; i++)
{
cin >> ti[i];
l = max(l, ti[i]);//记录最大时间
r += ti[i];//记录总时间
}
// 二分任务的时间
while (l <= r)
{
int mid = (l + r) / 2;
if (check(mid))
{
r = mid - 1;
ans = mid;
}
else
{
l = mid + 1;
}
}
print(ans);
return 0;
}