Hướng dẫn giải của Cắt dãy (đề HSG 12 Khánh Hòa 2020-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
Mỗi nhát cắt chia một đoạn thành hai. Với cuộn $i$, đặt $fi = \lfloor Li / M \rfloor$ là số đoạn dài $M$ tối đa lấy được. Nếu $\sum fi < K$ thì in $-1$. Lấy $qi$ đoạn từ cuộn $i$ với $\sum q_i = K$ thì số nhát cắt là:
- $q_i = 0$: không cắt, chi phí $0$.
- $qi = fi$ và $M \mid Li$: chi phí $qi - 1$ (đoạn cuối vừa khít, không còn thừa).
- Các trường hợp khác: chi phí $q_i$.
Như vậy mỗi đoạn tốn 1 nhát, trừ khi lấy hết một cuộn chia hết cho $M$ thì được giảm 1 nhát.
Sub 1: Quy hoạch động — ~O(N \cdot K \cdot \max f)~, dùng khi ~N \le 50, K \le 50~
Gọi $dp[j]$ là số nhát ít nhất để lấy đúng $j$ đoạn từ các cuộn đã xét. Với mỗi cuộn thử mọi $q$ từ $0$ đến $f_i$ (không quá $K$).
Nếu chỉ nộp sub này: đúng 12/20 test (8 test lớn quá giờ).
Sub 2: Tham lam — ~O(N \log N)~
Số nhát cắt $= K - $ (số cuộn chia hết cho $M$ được lấy hết). Vì vậy cần chọn nhiều cuộn chia hết nhất sao cho tổng $f$ của chúng không vượt $K$: sắp các $f$ tăng dần rồi lấy dần. Phần còn lại của $K$ lấy từ các cuộn khác, mỗi đoạn tốn đúng 1 nhát.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file CUTLINE.inp, ghi ra CUTLINE.out. Nếu $N \le 50$ và $K \le 50$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int N;
long long K, M;
vector<long long> L;
// So nhat can cat de lay q doan dai M tu cuon thu i (q <= f = floor(L_i / M)).
// - q = 0: khong cat.
// - q = f va L_i chia het cho M: chi can q - 1 nhat (doan cuoi vua khit, khong con thua).
// - con lai: moi doan can 1 nhat (con thua hoac chua cat het).
long long costOf(int i, long long q) {
if (q == 0) return 0;
long long f = L[i] / M;
if (q == f && L[i] % M == 0) return q - 1;
return q;
}
// Sub 1: quy hoach dong, dung khi N <= 50 va K <= 50.
// dp[j] = so nhat it nhat de lay dung j doan tu cac cuon da xet.
void sub1() {
const long long INF = LLONG_MAX / 4;
vector<long long> dp(K + 1, INF);
dp[0] = 0;
for (int i = 0; i < N; i++) {
vector<long long> nd(K + 1, INF);
long long f = L[i] / M;
for (long long j = 0; j <= K; j++) {
if (dp[j] >= INF) continue;
for (long long q = 0; q <= f && j + q <= K; q++)
nd[j + q] = min(nd[j + q], dp[j] + costOf(i, q));
}
dp = nd;
}
if (dp[K] >= INF) cout << -1 << "\n";
else cout << dp[K] << "\n";
}
// Sub 2: tham lam, dung cho moi du lieu.
// Tong nhat = K - (so cuon chia het cho M ma ta lay HET). Lay cac cuon chia het
// cho M co f nho nhat truoc de duoc nhieu cuon nhat ma tong f khong vuot K.
void sub2() {
long long total = 0;
vector<long long> fullDiv; // f cua cac cuon chia het cho M
for (int i = 0; i < N; i++) {
long long f = L[i] / M;
total += f;
if (f > 0 && L[i] % M == 0) fullDiv.push_back(f);
}
if (total < K) { // khong du doan dai M
cout << -1 << "\n";
return;
}
sort(fullDiv.begin(), fullDiv.end());
long long used = 0, cnt = 0;
for (long long f : fullDiv) {
if (used + f > K) break;
used += f;
cnt++;
}
cout << K - cnt << "\n";
}
int main() {
freopen("CUTLINE.inp", "r", stdin);
freopen("CUTLINE.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> K >> M;
L.resize(N);
for (auto &x : L) cin >> x;
if (N <= 50 && K <= 50) sub1();
else sub2();
return 0;
}
Bình luận