Hướng dẫn giải

Chọn nhiều học sinh nhất sao cho hai người bất kỳ trong đội chênh kỹ năng không quá 5. Đội hợp lệ khi và chỉ khi hiệu giữa kỹ năng lớn nhất và nhỏ nhất không quá 5, nên bài toán trở thành: tìm đoạn giá trị ~[v, v + 5]~ chứa nhiều phần tử nhất.

Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 100~

Coi mỗi học sinh ~i~ là người có kỹ năng nhỏ nhất của đội, đếm số học sinh có kỹ năng trong ~[a_i, a_i + 5]~, lấy giá trị lớn nhất. Nếu chỉ nộp sub này: đúng 10/20 test (các test lớn bị quá thời gian).

Sub 2: Sắp xếp và hai con trỏ — ~O(n \log n)~

Sắp xếp dãy tăng dần. Với mỗi vị trí ~r~, con trỏ ~l~ là vị trí nhỏ nhất sao cho ~a_r - a_l \le 5~; ~l~ chỉ tăng lên khi ~r~ tăng nên tổng cộng ~O(n)~ sau khi sắp xếp. Kết quả là ~\max(r - l + 1)~. Đúng 20/20 test.

Chương trình hoàn chỉnh

Hàm ~main~ đọc dữ liệu; nếu ~n \le 100~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

#include <bits/stdc++.h>
using namespace std;

int n;
long long a[200005];

// Sub 1: vét cạn ~O(n^2)~ — coi a[i] là kỹ năng nhỏ nhất, đếm người trong [a[i], a[i]+5]
void sub1() {
    int best = 0;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++)
            if (a[j] >= a[i] && a[j] <= a[i] + 5) cnt++;
        best = max(best, cnt);
    }
    cout << best << "\n";
}

// Sub 2: sắp xếp + hai con trỏ ~O(n log n)~
void sub2() {
    sort(a, a + n);
    int best = 0, l = 0;
    for (int r = 0; r < n; r++) {
        while (a[r] - a[l] > 5) l++;
        best = max(best, r - l + 1);
    }
    cout << best << "\n";
}

int main() {
    freopen("BALANCED.INP", "r", stdin);
    freopen("BALANCED.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    if (n <= 100) sub1();
    else sub2();
}