1028. 复制书稿
题意
现在要把 m 本有顺序的书分给 k个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。
复制时间为抄写页数最多的人用去的时间。
思路
因为是求 k 个人中用时最大的最小值 可以想到用二分来解决
mid 为假设的分组后用时最多的那个人消耗的时间
所以把原数组分成区间和小于等于mid 的cnt 段
如果cnt>k 说明 mid 选小了
否则表示mid 选大了 或者mid 正好是解
求出最大值应该是多少之后 再check 一边后就得到了符合题意的分组方式
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 600; int m, k; int a[N]; int L[N], R[N]; bool check(int x) { int sum = 0; int cnt = 1; R[cnt] = m; for (int i = m; i >= 1; --i) { if (sum + a[i] <= x) sum += a[i]; else { L[cnt] = i + 1; R[++cnt] = i; sum = a[i]; } } L[cnt] = 1; return cnt <= k; } void solve() { cin >> m >> k; for (int i = 1; i <= m; ++i) { scanf("%d", &a[i]); } int l = 1, r = 1e9; while (l < r) { int mid = l + r >> 1; if (check(mid))r = mid; else l = mid + 1; } check(l); for (int i = k; i >= 1; --i) { printf("%d %d\n", L[i], R[i]); } } int main() { solve(); return 0; }
