MT3020 任务分配

思路：利用二分找到某个时间是满足“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];}elsea[s] += ti[i];}if (s > k){ // 人数>kreturn 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;elsecout << 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;
}