← 返回题目列表

AtCoder · awc0056_b

B. 节能策略

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥的公司有 N 设备,每个设备都消耗电力。

当前功耗 i第一个设备 (1 \leq i \leq N) is A_i 瓦。高桥必须准确选择 K 来自这些的设备 N 设备并将其设置为“节能模式”。

设备设置为节能模式后,功耗变为原来功耗的一半,小数部分被丢弃。也就是说,如果一个设备有功耗 A_i 瓦特设置为节能模式,其功耗变为 \lfloor A_i / 2 \rfloor 瓦。在这里, \lfloor x \rfloor 表示不超过的最大整数 x。未设置节能模式的设备的功耗仍然存在 A_i 瓦。

每个设备要么设置为节能模式,要么不设置,并且同一设备不能选择多次。

Takahashi 希望通过选择最小化所有设备的总功耗 K 设备明智地设置为节能模式。

求最小总功耗。

约束

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

输入

N K
A_1 A_2 \cdots A_N
  • 第一行包含一个整数 N 表示设备数量和一个整数 K 代表要设置为节能模式的设备数量,以空格分隔。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个设备的功耗,以空格分隔。

输出

一行打印准确时所有设备的最小总功耗 K 设备设置为节能模式。


示例输入 1

5 2
10 7 3 8 5

示例输出 1

24

示例输入 2

4 4
100 50 30 20

示例输出 2

100

示例输入 3

8 3
1000000000 999999999 500000000 123456789 987654321 111111111 222222222 333333333

示例输出 3

2783950614