← 返回题目列表

AtCoder · awc0033_b

B. 工厂温度管理

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

分数: 300 分

问题陈述

高桥的爱好是种植室内植物,他家里养了很多植物。

高桥的房子有 N 房间,每间都配有空调。当前温度 i第一个房间是 T_i 度。

高桥正在种植的植物无法茁壮成长,除非室温至少为 L 度,最多 R 度。因此,如果放置植物的房间温度超出这个范围,就必须使用空调来调节温度。

当空调器在以下环境中使用时 i第一个房间,房间温度可以更改为任何所需的温度。电费为 1 日元每 1 温度变化程度。也就是说,改变温度的成本 T_i 度至 S 度是 |T_i - S| 日元。如果室温已经至少 L 度,最多 R 度,无需调整,成本为 0 日元。

高桥将选择 K 与 N 房间,将所有选定房间的温度调整为至少 L 度,最多 R 度,并将植物放入其中。

找出当 K 房间是最优选择的。

约束

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

输入

N K L R
T_1 T_2 \ldots T_N
  • 第一行包含四个空格分隔的整数: N 代表房间数量, K 代表要选择的房间数, L 代表适合温度的下限,以及 R 代表适宜温度的上限。
  • 第二行包含空格分隔的整数 T_1, T_2, \ldots, T_N 代表每个房间的当前温度。

输出

一行打印选择所需的最低总电费 K 房间并将所有温度调整为至少 L 度,最多 R 度。


示例输入 1

5 3 18 22
15 18 25 21 30

示例输出 1

3

示例输入 2

4 2 0 0
-5 7 0 3

示例输出 2

3

示例输入 3

8 5 -2 4
-10 -2 0 3 5 8 -1 12

示例输出 3

1

示例输入 4

18 10 100 130
80 95 99 100 101 110 120 130 131 140 150 70 85 128 129 90 105 160

示例输出 4

2

示例输入 5

1 1 -1000000000 -1000000000
1000000000

示例输出 5

2000000000