Tóm tắt đề bài

Cho \(N\) cuốn sách có giá \(a_1, a_2, \ldots, a_N\) và cần chọn đúng \(M\) cuốn. Hãy tìm giá trị nhỏ nhất của độ chênh lệch giữa cuốn đắt nhất và rẻ nhất trong \(M\) cuốn được chọn, tức là tối thiểu hóa \(\max - \min\).

Phân tích

• Ta cần chọn một tập con đúng \(M\) phần tử sao cho \(\max(a) - \min(a)\) nhỏ nhất.
• Nhận xét then chốt:
  • Nếu sắp xếp dãy giá tăng dần \(a\), thì với một đoạn liên tiếp độ dài \(M\), giá nhỏ nhất là phần tử đầu và lớn nhất là phần tử cuối.
  • Lời giải tối ưu luôn có thể biểu diễn bằng một đoạn liên tiếp trong mảng đã sắp xếp (vì nếu chọn \(M\) phần tử bất kỳ, chúng có thể “nằm trong” khoảng từ min đến max; để khoảng nhỏ nhất, ta chỉ cần xét các khoảng chứa đúng \(M\) giá gần nhau nhất sau khi sort).
• Ràng buộc lớn: \(N \le 10^7\) nên cần chú ý:
  • Đọc input nhanh.
  • Sắp xếp nhanh/ổn định về thời gian. Code AC dùng radix sort cho số 64-bit để nhanh hơn std::sort trong nhiều trường hợp.

Hướng giải quyết

Ý tưởng

1. Sắp xếp mảng giá \(a\) tăng dần.
2. Trượt cửa sổ (sliding window) độ dài \(M\) trên mảng đã sắp xếp:
   • Với mỗi \(i\) từ \(0\) đến \(N-M\):
     • Độ chênh lệch của cửa sổ \([i, i+M-1]\) là \(a_{i+M-1} - a_i\).
   • Lấy giá trị nhỏ nhất trong các độ chênh lệch đó.

Tại sao chỉ cần xét các đoạn liên tiếp sau khi sắp xếp?

Giả sử ta chọn \(M\) cuốn bất kỳ, sau khi sắp xếp các giá được chọn, độ chênh lệch là phần tử lớn nhất trừ phần tử nhỏ nhất. Trong mảng đã sắp xếp, tất cả các giá nằm giữa hai đầu mút đó tạo thành một đoạn liên tiếp; để có đúng \(M\) cuốn với khoảng nhỏ nhất, ta chỉ cần xét các đoạn liên tiếp dài \(M\) (các “cụm” \(M\) phần tử gần nhau nhất).

Liên hệ với code AC

• Code dùng bộ đọc nhanh tự cài (read_ll) để chịu được dữ liệu rất lớn.
• Thay vì std::sort, code dùng radix_sort cho uint64_t (8 bit mỗi lượt, tổng 8 lượt cho 64 bit):
  • Độ phức tạp gần như \(O(8N)\), thường nhanh và ổn định với \(N\) lớn.
  • Vì \(a_i \le 10^{15}\) nên không âm, ép kiểu sang uint64_t là an toàn.
• Sau khi sort, code duyệt \(i = 0..N-M\) và cập nhật min_diff.

Lưu ý/pitfall thường gặp

• Dùng kiểu long long cho giá và hiệu, vì \(a_i\) tới \(10^{15}\).
• Với \(N\) rất lớn, cin/cout thường không đủ nhanh nếu không tối ưu; cần fast I/O.
• Nếu dùng std::sort với \(N=10^7\) vẫn có thể AC tùy máy và time limit, nhưng radix sort giúp an toàn hơn.

Độ phức tạp

• Thời gian:
  • Radix sort 64-bit theo byte: \(O(8N)\).
  • Quét cửa sổ: \(O(N)\).
  • Tổng: \(O(N)\) (với hằng số nhỏ).
• Bộ nhớ:
  • Mảng \(a\): \(O(N)\).
  • Mảng phụ trong radix sort: \(O(N)\).
  • Tổng: \(O(N)\).