/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はオフィスビルの管理人です。夏の暑い日、各部屋のエアコンが故障してしまい、部屋の温度が上がりすぎてしまいました。
ビルには N 個の部屋があり、部屋 i (1 \leq i \leq N) の現在の室温は T_i 度です。社員が快適に仕事できるよう、すべての部屋の温度を目標温度 M 度以下にする必要があります。
高橋君は冷却パックを必要なだけいくつでも使うことができます。冷却パック 1 個を使うと、選んだ 1 つの部屋の温度をちょうど D 度下げることができます。冷却パックは部分的に使うことはできず、1 個あたり必ず D 度ちょうど下がります。同じ部屋に対して冷却パックを複数個使うこともでき、その結果として部屋の温度が M 度を大きく下回ったり、負の値になったりしても構いません。
すべての部屋の温度を M 度以下にするために必要な冷却パックの最小個数を求めてください。
制約
- 1 \leq N \leq 10^5
- 0 \leq M \leq 10^9
- 1 \leq D \leq 10^9
- 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N M D T_1 T_2 \ldots T_N
- 1 行目には、部屋の個数を表す整数 N 、目標温度を表す整数 M 、冷却パック 1 個で下げられる温度を表す整数 D が、スペース区切りで与えられる。
- 2 行目には、各部屋の現在の温度を表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
出力
すべての部屋の温度を M 度以下にするために必要な冷却パックの最小個数を整数で 1 行に出力してください。
入力例 1
3 25 5 30 28 20
出力例 1
2
入力例 2
5 20 3 35 20 29 18 25
出力例 2
10
入力例 3
10 100 7 150 99 200 100 85 163 101 50 120 142
出力例 3
42
Score : 300 pts
Problem Statement
Takahashi is the building manager of an office building. On a hot summer day, the air conditioner in each room has broken down, causing the room temperatures to rise too high.
The building has N rooms, and the current temperature of room i (1 \leq i \leq N) is T_i degrees. To ensure employees can work comfortably, the temperature of every room must be brought to at most the target temperature of M degrees.
Takahashi can use as many cooling packs as needed. Using 1 cooling pack lowers the temperature of one chosen room by exactly D degrees. A cooling pack cannot be used partially; each pack always lowers the temperature by exactly D degrees. Multiple cooling packs can be used on the same room, and it is acceptable if a room's temperature drops well below M degrees or even becomes negative as a result.
Find the minimum number of cooling packs needed to bring the temperature of every room to M degrees or below.
Constraints
- 1 \leq N \leq 10^5
- 0 \leq M \leq 10^9
- 1 \leq D \leq 10^9
- 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N M D T_1 T_2 \ldots T_N
- The first line contains three space-separated integers: N representing the number of rooms, M representing the target temperature, and D representing the temperature decrease per cooling pack.
- The second line contains space-separated integers T_1, T_2, \ldots, T_N representing the current temperature of each room.
Output
Print a single integer on one line: the minimum number of cooling packs needed to bring the temperature of every room to M degrees or below.
Sample Input 1
3 25 5 30 28 20
Sample Output 1
2
Sample Input 2
5 20 3 35 20 29 18 25
Sample Output 2
10
Sample Input 3
10 100 7 150 99 200 100 85 163 101 50 120 142
Sample Output 3
42