Thử thách
Đề bài
Bờm rất thích chơi với những con số. Để thử thách cậu ta, thầy giáo đã giao cho Bờm một bài toán. Thầy đưa cho Bờm $N$ số nguyên. Sau đó thầy sẽ chọn ngẫu nhiên 1 số tự nhiên $M$. Yêu cầu của thầy rất đơn giản: chia $N$ số nguyên vào $M$ nhóm sao cho tổng chi phí của $M$ nhóm là nhỏ nhất có thể. Chi phí của 1 nhóm được tính bằng chênh lệch giữa phần tử có giá trị lớn nhất và bé nhất trong nhóm đó. Nếu 1 nhóm có 0 hoặc 1 phần tử, chi phí của nhóm đó bằng 0.
Bờm rất giỏi trong việc tính toán, nhưng cậu ta lại không biết gì về lập trình. Bạn hãy giúp Bờm tìm cách phân chia $N$ số vào $M$ nhóm sao cho tổng chi phí là nhỏ nhất có thể.
Dữ liệu vào:
- Dòng đầu tiên chứa 2 số nguyên $N, M$ $(0 < N, M \le 1\,000\,000)$.
- Dòng thứ 2 chứa $N$ số nguyên $a_1, a_2, \ldots, a_N$ tương ứng với $N$ số nguyên thầy giáo đưa cho Bờm $(0 \le a_i \le 10^{10})$.
Dữ liệu ra: gồm một dòng duy nhất chứa tổng chi phí nhỏ nhất có thể để chia $N$ số vào $M$ nhóm.
Ràng buộc: có 60% số điểm tương ứng với $N, M \le 200$; 40% số điểm còn lại tương ứng với các điều kiện còn lại.
8 3
5 2 3 10 7 2 6 84Giải thích ví dụ: chia thành 3 nhóm $(5, 7, 6, 8)$, $(10)$ và $(2, 3, 2)$, chi phí từng nhóm tương ứng là $8 - 5 = 3$, $10 - 10 = 0$, $3 - 2 = 1$ → tổng chi phí là $4$.
int (khoảng $2.1 \cdot 10^9$), nên phải đọc và tính bằng long long.Lời mở đầu
Bài này nhìn qua giống bài chia nhóm phải thử rất nhiều cách, nhưng chỉ cần một quan sát về thứ tự là mọi thứ trở nên đơn giản: sau khi sắp xếp, mỗi nhóm tốt nhất là một đoạn liên tiếp. Từ đó mình đi qua 2 cách: quy hoạch động $O(M N^2)$ cho subtask nhỏ, rồi một nhận xét tham lam rất gọn chạy trong $O(N \log N)$.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, chia thành các nhóm sau:
| Test | N | M | Giá trị $a_i$ | Số test có số trùng | Đáp án |
|---|---|---|---|---|---|
| 1 – 30 | 8 … 20 | 2 … 18 | 1 … 993 | 22 | 0 … 531 |
| 31 – 60 | 200 … 200 | 12 … 97 | 1 … 9 972 018 756 | 30 | 77 783 … 1 695 076 517 |
| 61 – 90 | 300 000 … 300 000 | 18 … 96 719 | 1 … 9 999 993 473 | 30 | 4 211 539 … 9 957 654 711 |
| 91 – 100 | 1 000 000 … 1 000 000 | 1 255 … 809 153 | 1 … 9 999 993 884 | 10 | 0 … 9 405 087 675 |
- Test 1 – 30: $N \le 20$, giá trị nhỏ ($\le 1000$); có 3 test đáp án bằng 0 (khi $M$ gần bằng $N$ và có số trùng nhau).
- Test 31 – 60: $N = 200$, $a_i$ đã lên tới gần $10^{10}$ → ai dùng
intsẽ sai ngay từ đây. - Test 61 – 90: $N = 3 \cdot 10^5$; test 91 – 100: $N = 10^6$, $M$ từ vài nghìn tới $809\,153$.
- Không test nào có $M \ge N$, nhưng code vẫn nên xử lý trường hợp này. Hầu hết các test có nhiều số trùng nhau (khoảng trống bằng 0).
Đúng 60% số test đầu thoả $N, M \le 200$ như đề nói. Bảng subtask:
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 |
|---|---|---|---|---|
| 1 (60%) | $N, M \le 200$ | 1 – 60 | ✔ | ✔ |
| 2 (40%) | $N$ tới $10^6$ | 61 – 100 | ✘ | ✔ |
Ý tưởngSắp xếp, nhóm là đoạn liên tiếp
Sắp xếp dãy tăng dần: $a_1 \le a_2 \le \ldots \le a_N$. Mình khẳng định: luôn có một cách chia tối ưu trong đó mỗi nhóm là một đoạn liên tiếp của dãy đã sắp xếp. Vì sao? Giả sử nhóm $X$ có min là $a_l$, max là $a_r$; chi phí của $X$ là $a_r - a_l$, bất kể bên trong có những số nào. Nếu có số $a_k$ ($l < k < r$) đang nằm ở nhóm khác thì chuyển $a_k$ sang $X$: chi phí của $X$ không đổi (min, max giữ nguyên), còn nhóm cũ của $a_k$ bớt 1 phần tử nên chi phí không tăng. Lặp lại đến khi mọi nhóm là đoạn liên tiếp.
Gọi khoảng trống $d_i = a_{i+1} - a_i$. Một nhóm là đoạn $a_l..a_r$ có chi phí $a_r - a_l = d_l + d_{l+1} + \ldots + d_{r-1}$ – đúng bằng tổng các khoảng trống bên trong nó. Chia dãy thành $M$ đoạn là chọn $M - 1$ chỗ cắt, và các khoảng trống bị cắt thì không tính vào chi phí:
Em nhập dãy số và $M$ rồi bấm Tiếp để xem các bước sắp xếp, tính khoảng trống và cắt:
Cách 1Quy hoạch động – ăn subtask 1
Khi đã biết mỗi nhóm là một đoạn liên tiếp của dãy sắp xếp, ta có thể quy hoạch động mà chưa cần nhận xét tham lam: gọi $f[j][i]$ là tổng chi phí nhỏ nhất khi chia $a_1..a_i$ thành đúng $j$ nhóm. Thử mọi vị trí $k$ để nhóm cuối là $a_{k+1}..a_i$:
Đáp án là $f[M][N]$. Nếu $M > N$ thì cho $M = N$ (các nhóm thừa để rỗng, chi phí 0).
- Mảng
a,fkhai báo kích thước 205 nên code chỉ dùng cho $N \le 200$ (subtask 1); với test lớn chương trình truy cập ngoài mảng. INF = LLONG_MAX / 2để cộng thêm vẫn không bị tràn số.- $k$ bắt đầu từ $j - 1$ vì $j - 1$ nhóm đầu cần ít nhất $j - 1$ phần tử.
Kết quả chạy thật: bản C++ đúng 60/100 test – trọn subtask 1 (test 1 – 60), test chậm nhất chỉ 0.02 giây. Từ test 61 trở đi chương trình bị lỗi chạy (RE) vì mảng chỉ khai báo 205 phần tử; mà dù có khai báo đủ thì $M \cdot N^2$ với $N = 3 \cdot 10^5$ cũng không thể kịp. Bản Python cũng đúng 60/100 (test 1 – 60, chậm nhất 0.85 giây).
Cách 2Tham lam: cắt M − 1 khoảng trống lớn nhất
Cài đặt đúng công thức ở phần ý tưởng: sắp xếp, tính mảng khoảng trống gap, sắp xếp giảm dần, lấy $a_{N} - a_1$ trừ đi $M - 1$ khoảng trống đầu tiên.
- Điều kiện
i < n - 1trong vòng trừ để không vượt mảnggapkhi $M > N$. - Mọi phép tính dùng
long longvì $a_i \le 10^{10}$. - Có thể thay
sort(gap...)bằngnth_elementđể được $O(N)$ sau khi sắp xếp $a$, nhưng bản dùngsortđã chạy rất nhanh.
Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất (test 94, $N = 10^6$) chạy 0.23 giây. Bản Python đúng 76/100: phần lớn các test $N = 3 \cdot 10^5$ và mọi test $N = 10^6$ bị quá 1 giây vì riêng việc đọc và sắp xếp $10^6$ số lớn trong Python đã tốn quá nhiều thời gian.
long long vì $a_i$ tới $10^{10}$.
Nhận xét
Đăng nhận xét