Bessie's Interview

题目描述

Bessie 正在寻找一份新工作！幸运的是，目前有 $K$ 位农夫正在招人并进行面试。由于工作竞争非常激烈，农夫们决定按照奶牛的报名顺序给她们编号并依次面试。在 Bessie 之前共有 $N$ 头奶牛报名，因此她的编号是 $N+1$ ($1 \leq K \leq N \leq 3 \cdot 10^5$)。

面试流程如下：在时间 $0$，对每个 $1 \leq i \leq K$，农夫 $i$ 将开始面试奶牛 $i$。当某位农夫完成一次面试后，他会立刻开始面试队伍中的下一头奶牛。如果有多位农夫在同一时间完成面试，那么下一头奶牛可以根据自己的偏好，在所有空闲的农夫中选择任意一位来面试。

对于每个 $1\le i\le N$，Bessie 已经知道奶牛 $i$ 的面试将恰好需要 $t_i$ 分钟（$1 \leq t_i \leq 10^9$）。然而，她并不知道每头奶牛对农夫的偏好。

由于这份工作对 Bessie 非常重要，她想仔细为面试做准备。为此，她需要知道自己将会在什么时候开始面试，以及哪些农夫有可能面试她。请帮助她找出这些信息！

输入格式

第一行包含两个整数 $N$ 和 $K$。 第二行包含 $N$ 个整数 $t_1 \dots t_N$。

输出格式

第一行输出 Bessie 的面试开始时间。 第二行输出一个长度为 $K$ 的比特串，其中第 $i$ 位为 $1$ 当且仅当农夫 $i$ 可能面试 Bessie，否则为 $0$。

6 3
3 1 4159 2 6 5

8
110

提示

除 Bessie 外共有 $6$ 头奶牛，并且有 $3$ 位农夫，面试流程如下： 在时间 $t = 0$，农夫 $1$ 面试奶牛 $1$，农夫 $2$ 面试奶牛 $2$，农夫 $3$ 面试奶牛 $3$。 在时间 $t = 1$，农夫 $2$ 完成对奶牛 $2$ 的面试并开始面试奶牛 $4$。 在时间 $t = 3$，农夫 $1$ 和农夫 $2$ 都完成了面试，此时有两种可能： 农夫 $1$ 面试奶牛 $5$，农夫 $2$ 面试奶牛 $6$。在这种情况下，农夫 $2$ 会在时间 $t = 8$ 完成面试并开始面试 Bessie。 农夫 $1$ 面试奶牛 $6$，农夫 $2$ 面试奶牛 $5$。在这种情况下，农夫 $1$ 会在时间 $t = 8$ 完成面试并开始面试 Bessie。 因此，Bessie 的面试将于时间 $t = 8$ 开始，她可能由农夫 $1$ 或农夫 $2$ 面试。 SCORING: 测试点 2-3：不存在两位农夫在同一时间完成面试。 测试点 4-9：$N\le 3\cdot 10^3$ 测试点 10-21：无额外限制。 题目贡献：Avnith Vijayram

标签: USACO|2024|Silver

来源

USACO|2024|Silver