Với một đa tập \(S=\{x_0,x_1,\ldots,x_{m-1}\}\), sắp xếp các phần tử theo thứ tự không tăng:

Trong bài này, trung vị được định nghĩa là phần tử lớn thứ \(\lceil m/2\rceil\):

Lưu ý rằng với số phần tử chẵn, định nghĩa này có thể khác định nghĩa trung vị thường gặp.

Cho dãy \([a_0,a_1,\ldots,a_{n-1}]\) và số nguyên dương \(k\le n\). Chọn

để chia dãy thành đúng \(k\) đoạn không rỗng \([0,b_1),[b_1,b_2),\ldots,[b_{k-1},n)\). Đặt \(b_0=0,b_k=n\) và

Độ cân bằng của phép chia là \(\operatorname{Median}(\{c_0,c_1,\ldots,c_{k-1}\})\). Hãy tìm độ cân bằng lớn nhất trong mọi cách chia.

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include median.h và cài đặt:

void init(int c, int t);

• c là số hiệu test; c=0 biểu thị dữ liệu mẫu.
• t là số bộ dữ liệu trong test.
• Bộ chấm gọi hàm đúng một lần khi chương trình bắt đầu.

int median(int n, int k, std::vector<int> a);

• Các tham số lần lượt là độ dài dãy, số đoạn và dãy đã cho.
• Hàm phải trả về độ cân bằng lớn nhất.
• Bộ chấm gọi hàm đúng t lần.

Khung khai báo:

#include "median.h"

Dữ liệu bộ chấm

• Dòng đầu chứa \(c,t\).
• Với mỗi trong \(t\) bộ dữ liệu:
• Dòng đầu chứa \(n,k\).
• Dòng tiếp theo chứa \(a_0,a_1,\ldots,a_{n-1}\).

Grader ghi một dòng đáp án cho mỗi bộ dữ liệu.

Ràng buộc

Gọi \(N\) là tổng các giá trị \(n\) trong một test.

• \(1\le t\le20\).
• \(5\le n\le10^6\).
• \(2\le k\le n\).
• \(N\le10^6\).
• \(1\le a_i\le n\).

Phân nhóm

Mỗi test có giá trị \(5\) điểm.

Tính chất A: \(a_i\le2\) với mọi \(0\le i<n\).

Ví dụ

0 2
10 4
6 5 1 9 2 3 10 7 4 8
10 5
5 7 3 10 8 2 9 1 6 4

9
8

Trong bộ đầu, có thể chia thành \([6,5,1]\), \([9,2]\), \([3,10]\), \([7,4,8]\). Trung vị các đoạn là \(5,9,10,7\), nên độ cân bằng là \(9\).

Trong bộ thứ hai, có thể chia thành \([5,7]\), \([3,10]\), \([8,2]\), \([9,1]\), \([6,4]\). Trung vị các đoạn là \(7,10,8,9,6\), nên độ cân bằng là \(8\).

Nguồn

CCF NOI 2026 - Ngày 2, bài Median. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.