1. Phân tích đề bài
- Chúng ta cần tìm một tổng trọng lượng cố định sao cho số lượng cặp thỏa mãn là nhiều nhất.
- Vì và trọng lượng , nên tổng trọng lượng của một cặp chỉ có thể nằm trong khoảng từ (1+1) đến (50+50).
- Chiến lược: Thử tất cả các giá trị có thể của và kiểm tra xem với mỗi , ta ghép được bao nhiêu cặp.
2. Ý tưởng thuật toán
Sử dụng phương pháp Duyệt toàn bộ (Brute-force) kết hợp với Mảng đánh dấu (Frequency Array).
- Đếm tần suất: Đếm số lần xuất hiện của mỗi trọng lượng trong mảng đầu vào. Gọi mảng này là
cnt. - Duyệt các tổng : Cho một vòng lặp chạy từ 2 đến (tất cả các tổng có thể xảy ra).
- Tính số cặp với mỗi :
- Với mỗi cố định, ta tính số cặp có thể tạo thành.
- Duyệt các trọng lượng từ đến :
- Nếu : Số cặp tạo được là .
- Nếu (hai người cùng cân nặng): Số cặp tạo được là .
- Cộng dồn số cặp lại để được kết quả cho giá trị hiện tại.
- Cập nhật kết quả: So sánh số cặp của hiện tại với kết quả lớn nhất (
max_teams) đã tìm được trước đó và cập nhật.
3. Các bước thực hiện (Pseudo-code)
Đọc t (số bộ test)
Với mỗi bộ test:
Đọc n
Đọc mảng w, lưu tần suất xuất hiện vào mảng cnt (ví dụ: cnt[x] là số người nặng x)
max_teams = 0
Duyệt s từ 2 đến 2*n:
current_teams = 0
Duyệt i từ 1 đến (s - 1) / 2:
j = s - i
Nếu j <= n: // Đảm bảo trọng lượng j hợp lệ
current_teams += min(cnt[i], cnt[j])
// Xử lý trường hợp 2 người bằng nhau (nếu s chẵn)
Nếu s là số chẵn:
current_teams += cnt[s / 2] / 2
max_teams = max(max_teams, current_teams)
In ra max_teams
4. Lưu ý khi cài đặt
- Giới hạn mảng: Vì , mảng đếm
cntchỉ cần kích thước khoảng 55 hoặc 105 là đủ. - Phạm vi duyệt: Tổng không nhất thiết phải duyệt đến , chỉ cần duyệt từ tổng nhỏ nhất có thể (min + min thứ 2) đến tổng lớn nhất có thể (max + max thứ 2) trong mảng, nhưng với nhỏ thì duyệt từ 2 đến 100 vẫn chạy rất nhanh.
- Độ phức tạp: hoặc , hoàn toàn thỏa mãn thời gian cho phép.