AT_abc203_f [ABC203F] Weed

题目描述

高桥君和青木君家里的院子里长着 $N$ 棵草，分别编号为草 $1$、草 $2$、$\ldots$、草 $N$，其中第 $i$ 棵草的高度为 $A_i$。他们决定按照以下方式来除草：

• 首先，青木君可以选择至多 $K$ 棵草并将其拔掉。

• 然后，高桥君会重复以下操作，直到院子里的草全部被拔掉为止：

  • 设剩下的草中高度最大的为 $H$。将所有高度大于 $\frac{H}{2}$ 的草一并拔掉。

青木君希望在使高桥君的操作次数最小的前提下，使自己拔掉的草的数量也最少。请你求出此时高桥君的操作次数以及青木君需要拔掉的草的数量。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请按顺序输出高桥君的操作次数和青木君拔掉的草的数量，用空格隔开。

输入输出样例 #1

输入 #1

4 1
2 3 4 9

输出 #1

2 1

输入输出样例 #2

输入 #2

3 3
2 3 5

输出 #2

0 3

输入输出样例 #3

输入 #3

9 8
137 55 56 60 27 28 133 56 55

输出 #3

1 4

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq K \leq N$
• $1 \leq A_i \leq 10^9$
• 所有输入均为整数。

样例解释 1

例如，如果青木君选择拔掉草 $4$（高度为 $9$），剩下的草中最高的是草 $3$，高度为 $4$。$\frac{4}{2}=2$，因为 $2 < 3$，$2 < 4$，所以第一次操作时高桥君可以同时拔掉草 $2$ 和草 $3$。之后，第二次操作时拔掉草 $1$，高桥君共需操作 $2$ 次。另一方面，无论青木君选择拔掉哪一棵草，高桥君都无法在 $1$ 次操作内完成。如果青木君一棵草也不拔，高桥君需要操作 $3$ 次，因此青木君为了让高桥君的操作次数最少，至少要拔掉 $1$ 棵草。

样例解释 2

如果青木君把所有草都拔掉，高桥君就不需要进行任何操作，显然这是操作次数最少的情况。

由 ChatGPT 4.1 翻译