Tìm Đỉnh Cực Đại Trên Dãy Đơn Điệu
Points
26
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ dãy số được cho trước).
Cho dãy số nguyên $A_1, A_2, \dots, A_N$ có tính chất bitonic chặt: tồn tại một chỉ số $P$ ($1 \le P \le N$) sao cho $A_1 < A_2 < \dots < A_P$ và $A_P > A_{P+1} > \dots > A_N$. Để tìm vị trí đỉnh $P$ trong bài toán tương tác, ta dùng chiến lược tìm kiếm nhị phân trên $[L, R]$ (ban đầu $L = 1, R = N$):
- Khi $L < R$, đặt $mid = \lfloor (L + R) / 2 \rfloor$ và hỏi hai giá trị $A_{mid}$ và $A_{mid+1}$ (chỉ tốn truy vấn cho những chỉ số chưa từng được hỏi trước đó).
- Nếu $A_{mid} < A_{mid+1}$, cập nhật $L = mid + 1$; ngược lại cập nhật $R = mid$.
- Khi $L = R$, kết thúc và kết luận đỉnh là $L$.
Hãy mô phỏng chiến lược này để tìm đỉnh $P$ và đếm số chỉ số phân biệt đã phải truy vấn.
Dữ liệu vào
- Dòng đầu ghi số nguyên $N$ ($2 \le N \le 10^5$).
- Dòng thứ hai ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ ($|A_i| \le 10^9$).
Dữ liệu ra
- Hai số nguyên: chỉ số đỉnh $P$ và số chỉ số phân biệt đã truy vấn.
Ví dụ
| Input | Output |
|---|---|
| 6 1 3 8 12 7 4 |
4 4 |
Giới hạn
- $2 \le N \le 10^5$
Community Discussion