Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

---

1681. Minimum Incompatibility – Độ chênh lệch nhỏ nhất (LeetCode, độ khó Hard)

Cho một mảng số nguyên nums và một số nguyên ~k~. Bạn cần chia mảng này thành ~k~ tập con có kích thước bằng nhau sao cho không có hai phần tử bằng nhau nào nằm trong cùng một tập con.

Độ chênh lệch (incompatibility) của một tập con là hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất của tập đó.

Hãy in ra tổng độ chênh lệch nhỏ nhất có thể của ~k~ tập con sau khi chia mảng một cách tối ưu, hoặc in ra -1 nếu không thể chia được.

Một tập con là một nhóm các số nguyên lấy từ mảng, không quan tâm thứ tự.

Dữ liệu vào

• Dòng đầu gồm 2 số nguyên ~n~ (số phần tử) và ~k~.
• Dòng thứ hai gồm ~n~ số nguyên nums[0], nums[1], ..., nums[n-1].

Kết quả

• Một số nguyên là đáp án của bài.

Giới hạn

• ~1 \le k \le n \le 16~, ~n~ chia hết cho ~k~.
• ~1 \le~ nums[i] ~\le n~

Sample Input 1

4 2
1 2 1 4

Sample Output 1

4

Giải thích

Cách chia tối ưu là [1,2] và [1,4]. Tổng độ chênh lệch là (2 - 1) + (4 - 1) = 4. Lưu ý chia [1,1] và [2,4] sẽ cho tổng nhỏ hơn, nhưng tập thứ nhất có 2 phần tử bằng nhau.

Sample Input 2

8 4
6 3 8 1 3 1 2 2

Sample Output 2

6

Giải thích

Cách chia tối ưu là [1,2], [2,3], [6,8] và [1,3]. Tổng độ chênh lệch là (2 - 1) + (3 - 2) + (8 - 6) + (3 - 1) = 6.

Sample Input 3

6 3
5 3 3 6 3 3

Sample Output 3

-1

Giải thích

Không thể chia thành 3 tập con mà không có hai phần tử bằng nhau trong cùng một tập.