思路：利用二分找到某个时间是满足“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; }
