Ghép cặp mũ bảo hiểm

Xem dưới dạng PDF

Gửi bài giải


Điểm: 20
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 64M
đầu vào: stdin
Đầu ra: stdout

Tác giả:
Kiểu bài tập

Bình và Nam tổ chức chuyến dã ngoại đi xe đạp cho cả lớp. Có \(N\) chiếc mũ bảo hiểm có kích thước lần lượt là \(A_1, A_2, \dots, A_N\) và \(N\) bạn học sinh có kích thước đầu lần lượt là \(B_1, B_2, \dots, B_N\). Một bạn học sinh cỡ đầu \(B_j\) chỉ có thể đội vừa chiếc mũ cỡ \(A_i\) nếu độ lệch kích cỡ giữa chúng không quá \(K\), tức là: \(|A_i - B_j| \le K\) Mỗi chiếc mũ chỉ được phát cho tối đa một học sinh và mỗi học sinh chỉ nhận tối đa một chiếc mũ. Hãy tìm số học sinh tối đa có thể nhận được mũ bảo hiểm phù hợp.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le N \le 10^5\), \(0 \le K \le 10^9\)).
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).
  • Dòng thứ ba chứa \(N\) số nguyên \(B_1, B_2, \dots, B_N\) (\(1 \le B_i \le 10^9\)).
Dữ liệu ra
  • In ra một số nguyên duy nhất là số lượng học sinh tối đa có được mũ phù hợp.
Ví dụ

Đầu vào:

4 5
10 20 30 40
12 15 35 48

Đầu ra:

3

Giải thích:

  • Đầu cỡ 12 có thể đội mũ cỡ 10.
  • Đầu cỡ 15 có thể đội mũ cỡ 20 (hoặc ngược lại).
  • Đầu cỡ 35 có thể đội mũ cỡ 30.
  • Đầu cỡ 48 không thể đội vừa mũ nào còn lại.

Nhận xét

Không có ý kiến tại thời điểm này.