4977：任务安排
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 任务安排
## 题目描述
某研究所新研发了一个项目。该项目有 $n$ 个研究任务待分配，任务编号为 $1$ ~ $n$ ；共有 $k$ 个研究员参与本项目，研究员编号为 $1$ ~ $k$ 。
出于任务保密的原则，对于任务分配有着一定的要求：
- 每个研究员必须分配任务列表中的一段编号连续的任务，当然，**只分配一个任务或者不分配任务**也是可以的。
- 同一个任务只能被同一个研究员领取，第 $i$ 个任务一旦分配给了某研究员，其他人员不得参与该任务。
- 为提升分配效率，拟定分配方式为：所有研究员按自己**编号从大到小的顺序**依次领取任务，每个研究员会尽可能多的领取任务。（可能会形成部分编号较小的研究员领取不到任务的情况）
请编程计算出合理的任务分配方案，使得项目完成时间尽可能的短；项目完成时间的计算方式为：最后一个完成任务的研究员，其完成任务的总时间。
## 输入格式
输入 $2$ 个整数 $n$ 和 $k$ 。
第 $2$ 行有 $n$ 个整数，第 $i$ 个整数 $t_i$ 表示编号为 $i$ 的任务耗时。
## 输出格式
输出**若干行**，每行 $2$ 个整数，第 $i$ 行代表某个**分配到任务的研究员**领到任务的起止编号（没有分配到任务的研究员不需要输出）。
请按照分配任务起止编号字典序从小到大的顺序输出。
## 样例
### 样例输入 1
```text
9 3
1 2 3 4 5 6 7 8 9
```
### 样例输出 1
```text
1 5
6 7
8 9
```
### 样例输入 2
```text
3 3
3 1 2
```
### 样例输出 2
```text
1 1
2 3
```
### 样例输入 3
```text
9 5
282 594 674 344 122 345 621 850 535
```
### 样例输出 3
```text
1 2
3 4
5 7
8 8
9 9
```
## 说明/提示
样例 $1$ 解释
共有 $9$ 个任务， $3$ 个研究员。
第 $1$ 个研究员领取了第 $1 \sim 5$ 这 $5$ 个任务，耗时分别为 $1$ $2$ $3$ $4$ $5$ ，他完成任务的总时间为 $15$ 。
第 $2$ 个研究员领取了第 $6 \sim 7$ 这 $2$ 个任务，耗时分别为 $6$ $7$ ，他完成任务的总时间为 $13$ 。
第 $3$ 个研究员领取了第 $8 \sim 9$ 这 $2$ 个任务，耗时分别为 $8$ $9$ ，他完成任务的总时间为 $17$ 。
因此项目完成的时间为 $17$ ，即第 $3$ 个研究员完成任务的时间。
数据范围
对于 $50\%$ 的数据，满足 $1 \le k \le n \le 100$ 。
对于 $100\%$ 的数据，满足 $1 \le k \le n \le 10^5$ ， $1 \le t_i \le 1000$ 。
---
**题目来源：** 24年8月-B组（才俊）