F - 杂草

得分：$600$ 分

问题描述

高橋和青木的花园里有 $N$ 个杂草，编号为杂草 $1$，杂草 $2$，$\ldots$，杂草 $N$。杂草 $i$ 的高度为 $A_i$。 高橋和青木打算拔掉这些杂草，操作如下：

• 首先，青木最多可以选择 $K$ 个杂草并拔掉。
• 然后，高橋将重复以下操作，直到所有的杂草都被拔掉。
  • 设 $H$ 为剩余杂草中最高的杂草的高度。一次性拔掉所有高度超过 $\frac{H}{2}$ 的杂草。

青木希望最小化高橋需要做的操作次数。他也希望通过拔掉尽量少的杂草来达到这个目标。 求高橋需要的操作次数和青木需要拔掉的杂草数。

约束

• $1 \leq N \leq 2\times 10^5$
• $0 \leq K \leq N$
• $1 \leq A_i \leq 10^9$
• 输入中的所有值都是整数。

输入

从标准输入中按如下格式给出：

$N$ $K$

$A_1$ $A_2$ $\ldots$ $A_N$

输出

按顺序输出高橋需要的操作次数和青木需要拔掉的杂草数，中间用一个空格分隔。

4 1
2 3 4 9

2 1

例如，假设青木选择了高度为 $9$ 的杂草 $4$ 并将其拔掉。那么，剩余杂草中最高的是高度为 $4$ 的杂草 $3$。 我们有 $\frac{4}{2}=2$，高橋会在第一次操作中拔掉杂草 $2$ 和 $3$，因为 $2<3$ 并且 $2<4$。然后，他会在第二次操作中拔掉杂草 $1$，完成工作，总共进行了两次操作。 另外，无论青木选择哪一个杂草，高橋都无法在一次操作中完成工作。

另外，如果青木一株杂草都不拔掉，高橋将需要做三次操作，因此青木必须拔掉至少一株杂草以最小化高橋需要的操作次数。

3 3
2 3 5

0 3

如果青木拔掉所有杂草，高橋将不需要做任何操作，这显然是可能的最小操作次数。

9 8
137 55 56 60 27 28 133 56 55

1 4