题目
现在要把 本有顺序的书分给 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。
现在请你设计一种方案，使得复制时间最短。
复制时间为抄写页数最多的人用去的时间。
输入格式
第一行两个整数 。
第二行 个整数，第 个整数表示第 本书的页数。
输出格式
共 行，每行两个整数，第 行表示第 个人抄写的书的起始编号和终止编号。
行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。
特殊说明，如果一个人没有被安排任何抄写任务，则可用 0 0 来表示。
数据范围
输入样例：
9 3
1 2 3 4 5 6 7 8 9
输出样例：
1 5
6 7
8 9
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <iostream>
#define N 510
using namespace std;
int a[N], L[N], R[N];
int n, m;
bool check(int sum)
{
int cnt = 1, s = 0;
R[cnt] = n;
for (int i = n; i; -- i)
{
if (s + a[i] <= sum) s += a[i];
else
{
L[cnt] = i + 1;
++ cnt;
R[cnt] = i;
s = a[i];
}
}
L[cnt] = 1;
return cnt <= m;
}
int main()
{
cin >> n >> m;
int l = 0, r = 1e9;
for (int i = 1; i <= n; ++ i) cin >> a[i], l = max(l, a[i]);
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
check(r);
for (int i = m; i; -- i) cout << L[i] << " " << R[i] << endl;
return 0;
}
|
