Chia bánh cho trẻ em

Buổi 12 — Greedy Algorithm greedy sorting two-pointers
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Có $N$ em nhỏ và $M$ chiếc bánh. Em nhỏ thứ $i$ có độ tham ăn là $g_i$ (cần một chiếc bánh có kích thước ít nhất là $g_i$ để hài lòng). Chiếc bánh thứ $j$ có kích thước là $s_j$. Mỗi em chỉ được nhận tối đa một chiếc bánh và mỗi chiếc bánh chỉ được phát cho tối đa một em. Hãy tìm số em nhỏ hài lòng tối đa.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $M$.
  • Dòng thứ hai chứa $N$ số nguyên $g_1, g_2, \dots, g_N$.
  • Dòng thứ ba chứa $M$ số nguyên $s_1, s_2, \dots, s_M$.
Dữ liệu ra

Một số nguyên duy nhất là số em nhỏ hài lòng tối đa.

Ví dụ
Input Output
3 2\n1 2 3\n1 1 1
2 3\n1 2\n1 2 3 2
Giới hạn
  • $1 \le N, M \le 10^5$
  • $1 \le g_i, s_j \le 10^9$
Draft saved