← 返回题目列表

AtCoder · awc0066_b

B. 智能手机电池

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

分数: 300 分

问题陈述

高桥正在计划旅行。

高桥有 N 智能手机。每部智能手机的编号为 1 to N和智能手机 i 目前的电池电量为 A_i %。电池电量以整数值进行管理,并且永远不会低于 0 %.

电池电量为 L % 或以下则断电且无法使用。因此,智能手机 i 与 A_i \leq L 目前已从一开始就断电。智能手机一旦关机,就永远无法再次使用。

高桥有一块手机电池。设当前时间为时间 0。时 0,高桥最多可以选择 K 智能手机(可能 0)从当前已开机的智能手机中选择并将其连接到移动电池。连接到移动电池的智能手机保持连接状态,直到所有处理完成为止 Y 已完成,在此期间他们的电池电量根本没有减少。无法中途断开连接或将连接切换到其他智能手机。此外,关闭的智能手机无法连接到移动电池。

移动电池连接完成后,每次 1,时间 2, \ldots,时间 Y,按此顺序执行以下操作:

  1. 电池消耗: 对于每部未连接移动电池且已开机的智能手机,其电池电量会减少 1 %.
  2. 断电检查: 对于未连接移动电池的智能手机,任何电池电量已变为 L % 或更少已断电。

高桥最优选择连接移动电池的智能手机时,求此时所有处理后立即开机(可用)的智能手机的最大数量 Y 已完成。连接到移动电池的智能手机如果已开机,也会被计算在内。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L \leq 99
  • 0 \leq K \leq N
  • 1 \leq Y \leq 100
  • 1 \leq A_i \leq 100
  • 所有输入均为整数

输入

N L K Y
A_1 A_2 \ldots A_N
  • 第一行包含 N 代表智能手机的数量, L 代表智能手机关闭时的电池电量阈值, K 代表移动电池可同时连接的智能手机的最大数量,以及 Y 表示经过的时间,以空格分隔。
  • 第二行包含 A_1, A_2, \ldots, A_N 代表每部智能手机的当前电池电量,以空格分隔。

输出

一行打印一次所有处理后立即开机的智能手机的最大数量 Y 已完成。


示例输入 1

5 10 2 5
50 12 8 30 14

示例输出 1

4

示例输入 2

8 20 3 10
100 35 25 50 18 30 22 80

示例输出 2

7

示例输入 3

10 0 1 50
100 48 51 30 75 50 60 10 49 55

示例输出 3

6