Copy Books

Problem Statement

现在要把 $m$ 本有顺序的书分给 $k$ 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

Input

第一行两个整数 $m,k$。

第二行 $m$ 个整数，第 $i$ 个整数表示第 $i$ 本书的页数。

Output

共 $k$ 行，每行两个整数，第 $i$ 行表示第 $i$ 个人抄写的书的起始编号和终止编号。 $k$ 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

Sample Input

1
2


9 3
1 2 3 4 5 6 7 8 9

Sample Output

Constraints

$1\le k \le m \le 500$。

Solving

二分区间，找到满足划分为k个区间时，区间和最大值最小的情况。

此时对区间最大值进行二分，找到满足划分为k个区间的情况下时，区间和最大值最小的情况。

随后由于如果有多解，则尽可能让前面的人少抄写。我们需要再从后往前遍历，将每个区间的左右边界收集当作答案去后续输出。

 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75


const int N = 501;
const int M = 0; 
int n,k;
int arr[N];
struct node
{
    int l,r;
}ans[N];
bool check(int x)//x表示抄写区间的最大值 我们要其最大值最小
{
    int num = 1;
    int temp = 0;
    for(int i=1;i<=n;i++)
    {
        if(temp + arr[i]<=x) temp += arr[i];
        else
        {
            temp = arr[i];
            num++;
        }
    }
    return num <= k;
}
void get(int l)
{
    int num = 1;
    int index = k;
    int temp = 0;
    ans[k].r = n;
    ans[1].l = 1;
    for(int i=n;i>=1;i--)
    {
        if(temp + arr[i]<=l) temp += arr[i];
        else
        {   
            temp = arr[i];
            num++;
            if(num==k)
            {   
                ans[index].l = i+1;
                ans[1].r = i;
                ans[1].l = 1;
                return;
            }
            ans[index--].l = i+1;
            ans[index].r = i;
        }
    }
}
void solve()
{
    cin >> n >> k;
    int l = 0,r = 0,mid;
    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
        l = max(l,arr[i]);
        r += arr[i];
    }
    while(l+1<r)
    {
        mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
    if(!check(l))
    {
        l = r;
    }
    get(l);
    for(int i=1;i<=k;i++)
    {
        cout << ans[i].l << ' ' << ans[i].r << endl;
    }
}