Score : $600$ points

问题描述

高桥和青木的花园里长了 $N$ 株杂草，分别命名为杂草 1、杂草 2、$\ldots$、杂草 $N$。其中第 $i$ 株杂草的高度为 $A_i$。高桥和青木决定按照以下方式拔除这些杂草：

• 首先，青木最多会选择 $K$ 株杂草并拔除它们。
• 然后，高桥将重复执行以下操作，直到所有杂草都被拔除：
  • 计算剩余杂草中最高的高度 $H$，然后一次性拔除所有高度大于 $\frac{H}{2}$ 的杂草。

青木希望尽可能减少高桥需要执行的操作次数，并希望通过拔除最少数量的杂草来实现这一目标。请找出在这种情况下高桥执行的操作次数以及青木拔除的杂草数量。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi's and Aoki's garden is covered with $N$ weeds, called Weed $1$, Weed $2$, $\ldots$, Weed $N$. The height of Weed $i$ is $A_i$. Takahashi and Aoki have decided to pull these weeds, as follows:

• First, Aoki will choose at most $K$ weeds and pull them.
• Then, Takahashi will repeat the following operation until all weeds are pulled.
  • Let $H$ be the height of the tallest remaining weeds. Pull all weeds with heights above $\frac{H}{2}$ at once.

Aoki wants to minimize the number of operations done by Takahashi. Also, he wants to minimize it by pulling the minimum number of weeds needed. Find the number of operations done by Takahashi and the number of weeds Aoki pulls in this case.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $0 \leq K \leq N$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

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

Output

Print the number of operations Takahashi will do and the number of weeds Aoki will pull, in this order, with a space in between.

Sample Input 1

4 1
2 3 4 9

Sample Output 1

2 1

For example, assume that Aoki chooses Weed $4$, with height $9$, and pulls it. Then, the tallest remaining weed is Weed $3$, with height $4$. We have $\frac{4}{2}=2$, and Takahashi will pull Weed $2$ and $3$ in the first operation, since $2<3$ and $2<4$. Then, he will pull Weed $1$ in the second operation, completing his work in two operations. On the other hand, he will not complete his work in one operation, no matter which one weed Aoki chooses.

Also, if Aoki pulls no weed, Takahashi will have to do three operations, so Aoki must pull at least one weed to minimize the number of operations done by Takahashi.

Sample Input 2

3 3
2 3 5

Sample Output 2

0 3

If Aoki pulls all weeds, Takahashi has to do zero operations, which is obviously the smallest number possible.

Sample Input 3

9 8
137 55 56 60 27 28 133 56 55

Sample Output 3

1 4

update @ 2024/3/10 09:16:38