Bài 3. Hàng rào (HSG THPT Thành phố Huế 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT Thành phố Huế 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

An là một cậu bé rất thông minh, luôn tự đặt ra cho mình những câu hỏi thú vị về vấn đề trong cuộc sống. Vào một ngày mưa lớn, khi nhìn qua khung cửa sổ, An thấy hàng rào nhà mình đang bị ngập một phần trong nước. Hàng rào nhà An được ghép liên tiếp bởi ~N~ thanh gỗ có độ cao khác nhau. Khi nước dâng lên từ từ, những thanh gỗ thấp hơn hoặc bằng mực nước sẽ bị ngập. Lúc này hàng rào bị chia cắt thành nhiều nhóm thanh gỗ riêng biệt. An muốn biết xem số nhóm nhiều nhất có thể xuất hiện tại cùng một thời điểm là bao nhiêu?

Trong suốt quá trình nước dâng, hãy xác định số nhóm thanh gỗ riêng biệt nhiều nhất có thể xuất hiện tại cùng một thời điểm.

Dữ liệu vào

Gồm các dòng:

  • Dòng 1: Chứa một số nguyên dương ~N (1 \le N \le 10^5)~.
  • ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~H_i~ tương ứng với độ cao của thanh gỗ thứ ~i (1 \le H_i \le 10^9)~.

Kết quả

Một dòng duy nhất là kết quả của bài toán.

Ví dụ

Input 1

6
2
1
1
5
1
2

Output 1

3

Giải thích:
Khi mực nước bằng 1, các thanh có độ cao 1 (vị trí 2, 3, 5) bị ngập, hàng rào còn ba nhóm rời nhau: {1}, {4}, {6}.

Ràng buộc

  • Có 40% số điểm tương ứng với ~N \le 1000~.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...