Bài 2. Xóa số (HSG THPT Bắc Ninh 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 Bắc Ninh 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy ~A~ gồm ~N~ phần tử nguyên ~A_1, A_2, \ldots, A_N~ và số nguyên dương ~K~. Khi thực hiện thao tác xóa ~K~ phần tử bất kì khỏi dãy ~A~ ta thu được dãy ~B~ gồm các phần tử còn lại của dãy ~A~. Gọi ~M~ là hiệu lớn nhất giữa hai số bất kỳ trong dãy ~B, m~ là hiệu không âm nhỏ nhất giữa hai số bất kỳ trong dãy ~B~.

Yêu cầu: Tìm giá trị nhỏ nhất của ~|M| + |m|~.

Dữ liệu vào

Dữ liệu vào từ thiết bị vào chuẩn gồm hai dòng:

  • Dòng 1: Ghi hai số nguyên dương ~N~ và ~K (3 \le N \le 10^6, 1 \le K \le N - 2)~;
  • Dòng 2: Ghi ~N~ số nguyên ~A_1, A_2, \ldots, A_N (|A_i| \le 5 \times 10^6; i = 1, 2, \ldots, N)~.

Kết quả

Ghi ra thiết bị ra chuẩn một giá trị duy nhất là kết quả của bài toán.

Ví dụ

Input 1

5 2
-3 -2 3 8 6

Output 1

7

Giải thích:
Có thể xóa hai số −3, −2 → dãy ~B = (3, 8, 6)~
→ ~M = 5; m = 2~ → kết quả bằng ~5 + 2 = 7~

Input 2

6 2
-5 8 10 1 13 -1

Output 2

13

Giải thích:
Có thể xóa hai số −5, 13 → dãy ~B = (8, 10, 1, -1)~
→ ~M = 11; m = 2~ → kết quả bằng ~11 + 2 = 13~

Ràng buộc

  • Subtask 1: Có 30% số test ứng với 30% số điểm có ~N \le 20~;
  • Subtask 2: Có 40% số test ứng với 40% số điểm có ~N \le 10^3~;
  • Subtask 3: Có 30% số test ứng với 30% số điểm có ~N \le 10^6~.

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). Vẫn có thể giữ đoạn freopen("XOASO.INP", ...) nếu đặt trong điều kiện if (fopen("XOASO.INP", "r")).


Đang tải...