trang chủ / bài tập / maxminseg

Cực đại của cực tiểu

Cho một dãy số nguyên $a_{1}, a_{2}, \dots, a_{n}$ và một số nguyên $k$ .

Bạn phải chia dãy thành đúng $k$ đoạn con liên tiếp, mỗi đoạn không rỗng. Nói cách khác, chọn các đoạn $[l_{1}, r_{1}], [l_{2}, r_{2}], \dots, [l_{k}, r_{k}]$ thoả mãn $l_{1} = 1$ , $r_{k} = n$ và $l_{i} = r_{i - 1} + 1$ với mọi $i > 1$ .

Với mỗi đoạn, tính giá trị nhỏ nhất của các phần tử trong đoạn đó. Sau đó lấy giá trị lớn nhất trong $k$ giá trị nhỏ nhất vừa tính.

Hãy tìm giá trị lớn nhất có thể đạt được.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $k$ : kích thước dãy và số đoạn phải chia.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra một số nguyên duy nhất: giá trị lớn nhất có thể đạt được.

Ràng buộc

$1 \leq k \leq n \leq 10^{5}$
$- 10^{9} \leq a_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 2 1 2 3 4 5	5	Chia thành $[1, 4]$ và $[5, 5]$ , được hai dãy $(1, 2, 3, 4)$ và $(5)$ . Hai giá trị nhỏ nhất là $1$ và $5$ , kết quả là $max (1, 5) = 5$ .
5 1 -4 -5 -3 -2 -1	-5	Chỉ có một cách chia là lấy cả dãy làm một đoạn, nên kết quả bằng giá trị nhỏ nhất của cả dãy là $- 5$ .
3 2 1 5 3	3	Phần tử lớn nhất là $5$ nhưng nằm ở giữa, với $k = 2$ nó luôn bị ghép chung với một trong hai đầu. Cách tốt nhất là $[1, 2]$ và $[3, 3]$ , cho $max (1, 3) = 3$ .
7 3 1 1 1 10 1 1 1	10	Chia thành $[1, 3]$ , $[4, 4]$ và $[5, 7]$ , tách riêng được phần tử $10$ , kết quả là $max (1, 10, 1) = 10$ .

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 3,00một phần

Giới hạn thời gian 1.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig