Loading... [题目链接](https://www.luogu.com.cn/problem/P1281) 首先,通关观察题意,发现是让我们选择分类。 那么我们一开始需要得到**最少的时间**这个变量。所以我们可以二分答案查找这个最少的时间。找到这个最少的时间之后再去枚举这个过程。当然这道题中,尽量让前面的人少抄写。也就是让后面的人多抄写,那就从后往前,尽可能的多拿,剩下的就是前面需要拿的。 Code: ```cpp // Problem: 书的复制 #include <iostream> #include <cstdio> using namespace std; const int MAXN = 501; int a[MAXN + 1]; int n, m; bool check(int x) { int cnt = 0, k = 1; for (int i = 1; i <= n; i ++ ) { if (a[i] > x) { return false; } if (cnt + a[i] > x) { k ++; cnt = a[i]; } else { cnt += a[i]; } } return k <= m; } pair<int, int> res[10001]; void getans(int x) { int k = m, f = 0; res[k].first = n; for (int i = n; i >= 1; i -- ) { f += a[i]; if (f > x) { f = a[i]; res[k].second = i + 1; k --; res[k].first = i; } } res[1].second = 1; for (int i = 1; i <= m; i ++ ) { printf("%d %d\n", res[i].second, res[i].first); } } int main() { int l, r; scanf("%d%d", &n, &m); l = 1; r = 100001; for (int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); } while(r - l > 5) { int mid = (r + l) / 2; if (check(mid)) { r = mid; } else { l = mid; } } int res = 0; for (int i = l; i <= r; i ++ ) { if (check(i)) { res = i; break; } } getans(res); return 0; } ``` 最后立个Flag, 这几天写一下二分答案的博客。 * [ ] 是否填坑 最后修改:2020 年 08 月 10 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 End.