题目传送门

第一道独立做出来的绿题祭（虽然花了我将近一个小时）

这是一道二分题目。

为了方便：

因为这道题没有明确的规定抄书时间（反正不影响结果），所以我们不妨假设一个人抄一页需要 $1$ 分钟。

确定二分范围

确定一下二分的范围：

最优情况：每个人都只抄一本，需要的时间为页数最大的那一本所需时间。

最坏情况：一个人要把所有书抄完，需要的时间为所有书加在一起的时间。

所以二分的范围就是从最大值到和。

核心代码

然后二分函数开始验证，注意验证的是当只给那么多时间的时候这些人可不可以完成抄写任务。二分的地方很简单，主要的部分其实是输出答案那一部分和 $check$ 函数。

首先先来看输出答案那一部分。

注意题目中的一句话：

如果有多解，则尽可能让前面的人抄写少的页数。

定义 $l$ 为需要的最小时间（也就是二分出来的答案）。

因为要求让前面的人抄得尽量少，意思就是说让后面的人抄得尽量多（这个点一定要倒着想，如果是从前到后的话需要搜索，这样会 TLE）。那么就写一个循环，只要这个人现在抄的时间不超过 $l$，就让他一直抄，直到再加上一个就会超过为止，这样就可以保证后面的人抄得最多。

打一个有注释的代码（输出部分）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int flag=n,c=0;//flag代表目前拿到的书的编号，c代表现在这个人抄的时间
for(int i=k;i>=1;i--){//枚举每一个人，要倒着枚举
    while(c+a[flag]<=l&&flag){//可以继续抄且有书可抄
        c+=a[flag];//这个人抄的时间增加
        flag--;//枚举下一本书
    }
    s[i]=flag+1;//这个人抄完了，存一下开始的编号
    c=0;//清空时间
}
for(int i=1;i<=k-1;i++){//输出：这个人抄书的结束点一定是下一个人的开始点-1
    printf("%d %d\n",s[i],s[i+1]-1);
}
printf("%d %d",s[k],n);//最后一个人的结束点是n，需要单独考虑
exit(0);//输出后直接结束程序

然后再看有关 $check$ 函数的那一部分。

本人采取的方法是：让每本书都被抄到，看在此时间内能否用小于等于 $k$ 个人完成任务。如果可以，就往小的部分二分，反之往大的方向二分。

写一下 $check$ 函数（也是一个有注释的代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(int x){ //x为当前判断的时间长度
    int r=1,c=0;//r：需要的人数 c：这个人当前抄书的时间
    for(int i=1;i<=n;i++){
        if(c+a[i]<=x)//可以继续抄这本书
            c+=a[i];
        else{//需要换下一个人抄这本书
            r++;
            c=a[i];
        }
    }
    if(r<=k)//答案是否小于等于总人数
        return true;
    return false;
}

一个问题：关于有人没活可以干

那么现在你可能会问一个问题了：题目中不是还有这么一句话吗？

且每个人都必须抄写。

你咋不判断呢？

那么我们来分析一下：

首先题目对人数有个要求：$k≤m≤500$

可见总人数是小于书的本数的。那么可以发现为了达到最短的时间，每个人都必须抄书，也就是说，最优解情况一定是每个人都会抄的。

可以证明这一点：假设有人没抄，现在必然有人的抄书时间是等于总用时的，如果耗时最大的人只抄了一本书，那么这个没抄的人可以去找一个抄多本书去“借”一本（题目的数据保证了如果有人没抄，那一定会有抄多本书的人），反正也不会影响结果。如果耗时最大的人抄了不止一本书，那么这个人可以帮他“分摊任务”，这样可以减小总用时，说明这一定不是最佳方案。可以得出：最优解一定是所有人都会抄书的。

洛谷的题目已经修正了不存在这种情况，但是鉴于我们 OJ 的毒瘤数据还是需要考虑一下这个点。当然你没考虑到也能 AC。

代码

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
#include<bits/stdc++.h>
using namespace std;
int n,k,sum,a[505],s[505];//sum是页数的和，s是输出的答案
bool check(int x){
    int r=1,c=0;
    for(int i=1;i<=n;i++){
        if(c+a[i]<=x)
            c+=a[i];
        else{
            r++;
            c=a[i];
        }
    }
    if(r<=k)
        return true;
    return false;
}
void f(int l,int r){
    if(l==r){//已经找到满足条件的页数 
        //计算与输出结果
        int flag=n,c=0;
        for(int i=k;i>=1;i--){
            while(c+a[flag]<=l&&flag){
                c+=a[flag];
                flag--;
            }
            s[i]=flag+1;
            c=0;
        }
        for(int i=1;i<=k-1;i++){
            printf("%d %d\n",s[i],s[i+1]-1);
        }
        printf("%d %d",s[k],n);
        exit(0);
    }
    int mid=(l+r)>>1;
    if(check(mid))
        f(l,mid);//因为答案就有可能是mid所以mid不能-1
    else
        f(mid+1,r);
    return;
}
int main(){
    int y=INT_MIN;//y为最大值
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
        y=max(y,a[i]);
    }
    f(y,sum);
    return 0;
}