99 . [Tutorial] 趕不完的作業 2

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

94.7% (18/19)

Submission's AC Ratio

69.2% (18/26)

Tags

tutorial

Description

有 $N$ 份作業，你知道每一份作業你都只需要 $L$ 小時就能寫完，但可怕的是，第 $i$ 份作業再過 $d_i$ 小時就要截止了！

想要讓所有作業在截止前完成可能還有些困難，因此，你希望能完成越多份作業越好。試問在最佳策略下，你能有幾份作業在截止時間前寫完？

*註：若一份作業 $L$ 小時後截止，你有辦法馬上開始寫這份作業來趕上死線

Input Format

輸入首行有兩個正整數 $N, L$，代表有 $N$ 份作業，且每完成一份作業需要 $L$ 小時。

接下來一行 $N$ 個正整數 $d_1, d_2, \ldots, d_N$，代表距離第 $i$ 份作業截止還有 $d_i$ 小時。

  • $1 \leq N \leq 2\times 10^ 5$
  • $1 \leq L, d_i \leq 10^ 9$

Output Format

輸出一行一個非負整數，代表在最佳策略下能趕上死線的作業份數。

Sample Input 1

5 2
3 1 4 1 5

Sample Output 1

2

Sample Input 2

6 2
2 3 2 3 3 5

Sample Output 2

2

Hints

Problem Source

程式解題社教學題。

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~14 無特別限制。 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
Submit
Back to Top