Trận đánh của Layton

Xem PDF

Điểm: 150 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một đất nước nọ đang trong tình cảnh chiến tranh. Một vị giáo sư tài giỏi có tên là Layton đã được mời đến để giúp nước.

Nhà vua ban cho giáo sư \(N\) quân đoàn, với quân đoàn thứ \(i\) sẽ có \(A_i\) số người. Biết rằng, đất nước đang có \(N\) mặt trận đang diễn ra, tại mặt trận \(j\) sẽ có \(E_j\) lính giặc đang đánh chiếm vùng đó.

Giả sử như Layton cử binh đoàn \(i\) có số quân là \(A_i\) đến mặt trận \(j\) có số địch là \(E_j\), nếu \(A_i \geq E_j\) thì chắc chắn tại mặt trận đó không thể thua được. Layton muốn biết, có tối thiểu bao nhiêu mặt trận Layton sẽ thua nếu ông điều binh tối ưu nhất. Biết rằng mỗi binh đoàn chỉ có thể được cử đến 1 mặt trận.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(N (1 \leq N \leq 2*10^5)\)
  • Dòng thứ hai, chứa \(N\) số nguyên dương \(A_i\) là số lính trong binh đoàn thứ \(i\) mà giáo sư Layton chỉ huy \((1 \leq A_i \leq 10^9)\)
  • Dòng thứ ba, chứa \(N\) số nguyên dương \(E_i\) là số lính giặc đang đánh chiếm mặt trận thứ \(i\) \((1 \leq E_i \leq 10^9)\)

Output

  • Một số nguyên dương duy nhất, là số mặt trận tối thiểu mà Giáo sư Layton thua nếu như ông cử người tối ưu.

Example

Test 1

Input
5
4 3 1 1 1
5 4 3 2 1
Output
2
Note

Hình bên trái là thứ tự mặc định quân đoàn. Với thứ tự như vậy, Layton sẽ thua đến \(4\) mặt trận. Hình bên phải là sau khi Layton điều quân, với cách như vậy, Layton chỉ thua \(2\) mặt trận.

Test 2

Input
3
1 2 3
3 4 5
Output
2

Bình luận


  • 0
    minhtuanitk20    11:41 p.m. 10 Tháng 11, 2021

    deque


    • 7
      longkold00    3:40 p.m. 5 Tháng 11, 2021

      bài này sort theo thứ tự giảm dần mảng a và cho mảng e vào hàng đợi ưu tiên với phần tử ở đỉnh là max