Hướng dẫn giải của Sắp xếp kiện hàng (đề Đồng Tháp 2021)
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có n kiện hàng xếp lần lượt theo thứ tự 1..n với tàu có sức chứa M. Ta được chọn một số kiện để lại cảng sao cho kiện k xếp được lên tàu, hỏi số kiện phải để lại ít nhất. Quan sát quan trọng: kiện k xếp được khi tổng khối lượng các kiện xếp trước nó không vượt T = M - a_k. Vậy các kiện 1..k-1 được xếp là một tập con có tổng <= T, và mọi kiện không được xếp đều phải để lại. Số kiện để lại ít nhất bằng (k - 1) trừ số kiện nhiều nhất xếp được với tổng <= T.
Sub 1: Vét cạn — ~O(2^n \cdot n)~, dùng khi ~n \le 20~
Thử mọi tập con các kiện trong 1..k-1 (dùng bitmask), tính tổng, nếu tổng <= T thì cập nhật số kiện lớn nhất. Đáp án là (k-1) - số kiện lớn nhất đó.
Nếu chỉ nộp sub này: đúng 6/20 test (chỉ các test có n <= 20 được tính, các test còn lại vượt miền của sub này).
Sub 2: Quy hoạch động — ~O(n^2)~, dùng khi ~n \le 1000~
Gọi dp[j] là tổng nhỏ nhất khi chọn đúng j kiện trong 1..k-1. Duyệt từng kiện, cập nhật dp[j] = min(dp[j], dp[j-1] + a_i) (duyệt j giảm dần để mỗi kiện chỉ chọn một lần). Số kiện lớn nhất có dp[j] <= T cho đáp án.
Nếu chỉ nộp sub 1 và 2 thì đúng mọi test có n <= 1000 (ép chạy riêng sub 2: 20/20 test).
Sub 3: Tham lam — ~O(n \log n)~, dùng cho mọi n
Sắp xếp các kiện 1..k-1 theo khối lượng tăng dần, rồi lấy lần lượt các kiện nhẹ nhất khi tổng còn <= T. Lý do: với cùng số lượng kiện, chọn các kiện nhẹ nhất là tổng nhỏ nhất, nên lấy được nhiều kiện nhất.
Bẫy cần chú ý: T = M - a_k có thể bằng 0; tổng có thể lên tới 10^5 · 10^9 nên dùng long long.
Ví dụ: với n = 8, M = 20, k = 6, a = 5 4 8 2 3 10 6 7 thì T = 10, các kiện 1..5 sắp thành 2 3 4 5 8, lấy được 3 kiện (2+3+4 = 9), đáp án là 5 - 3 = 2.
Chương trình hoàn chỉnh
main đọc dữ liệu rồi chọn sub theo n: n <= 20 gọi sub1, n <= 1000 gọi sub2, còn lại gọi sub3. Khi đi thi, nên viết như vậy: sub sau có lỗi thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long M;
long long a[100005]; // a[1..n]
// Nhận xét: kiện k được xếp khi tổng khối lượng các kiện xếp trước nó <= T = M - a[k].
// Các kiện 1..k-1 hoặc được xếp (tổng khối lượng phải <= T) hoặc bị để lại.
// Muốn để lại ít kiện nhất thì muốn xếp nhiều kiện nhất với tổng <= T:
// đáp án = (k - 1) - (số kiện xếp được nhiều nhất trong 1..k-1 với tổng <= T).
// Sub 1: vét cạn — thử mọi tập kiện trong 1..k-1, lấy tập có nhiều kiện nhất mà tổng <= T. Dùng khi n <= 20.
void sub1() {
int m = k - 1;
long long T = M - a[k];
int best = 0;
for (int mask = 0; mask < (1 << m); mask++) {
long long sum = 0;
for (int i = 1; i <= m; i++)
if (mask >> (i - 1) & 1) sum += a[i];
if (sum <= T) best = max(best, __builtin_popcount(mask));
}
cout << m - best << "\n";
}
// Sub 2: quy hoạch động dp[j] = tổng nhỏ nhất khi chọn đúng j kiện trong 1..k-1. O(n^2). Dùng khi n <= 1000.
void sub2() {
int m = k - 1;
long long T = M - a[k];
const long long INF = LLONG_MAX / 4;
vector<long long> dp(m + 1, INF);
dp[0] = 0;
for (int i = 1; i <= m; i++)
for (int j = i; j >= 1; j--) // duyệt ngược để mỗi kiện chỉ dùng một lần
if (dp[j - 1] < INF) dp[j] = min(dp[j], dp[j - 1] + a[i]);
int best = 0;
for (int j = 0; j <= m; j++)
if (dp[j] <= T) best = j;
cout << m - best << "\n";
}
// Sub 3: sắp xếp các kiện 1..k-1 tăng dần rồi lấy dần kiện nhẹ nhất khi còn đủ chỗ. O(n log n).
void sub3() {
int m = k - 1;
long long T = M - a[k];
vector<long long> v(a + 1, a + m + 1);
sort(v.begin(), v.end());
long long sum = 0;
int cnt = 0;
for (long long x : v) {
if (sum + x > T) break; // kiện nhẹ nhất tiếp theo đã không xếp được
sum += x;
cnt++;
}
cout << m - cnt << "\n";
}
int main() {
freopen("kienhang.inp", "r", stdin);
freopen("kienhang.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> M >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 20) sub1(); // dữ liệu nhỏ: vét cạn
else if (n <= 1000) sub2(); // n vừa: quy hoạch động
else sub3(); // n lớn: tham lam
return 0;
}
Bình luận