Hướng dẫn giải của Làm việc nhà (đề TP.HCM 2021)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Chọn được nhiều việc nhất trong thời gian T.
Sub 1: Vét cạn, ~O(2^C \cdot C)~
Duyệt mọi tập con việc, giữ tập có tổng thời gian ≤ T và số việc lớn nhất. Nếu chỉ nộp sub này: đúng 5/20 test.
Sub 2: Tham lam, ~O(C \log C)~
Sắp xếp thời gian tăng dần, làm việc ngắn nhất trước cho đến khi hết giờ. Đúng 20/20 test.
Chương trình hoàn chỉnh
main: C ≤ 20 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long T; // gioi han thoi gian
int C; // so viec nha
vector<long long> t; // thoi gian can de lam tung viec
// Sub 1: vet can. Thu moi tap con cac viec (2^C tap), chi nhan tap co tong thoi gian <= T
void sub1() {
int best = 0;
for (int mask = 0; mask < (1 << C); mask++) {
long long sum = 0;
int cnt = 0;
for (int i = 0; i < C; i++)
if (mask >> i & 1) {
sum += t[i];
cnt++;
}
if (sum <= T) best = max(best, cnt);
}
cout << best << "\n";
}
// Sub 2: tham lam. Sap xep thoi gian tang dan, lam tu viec ngan nhat cho den khi het gio
void sub2() {
sort(t.begin(), t.end());
long long sum = 0;
int cnt = 0;
for (int i = 0; i < C; i++) {
if (sum + t[i] > T) break;
sum += t[i];
cnt++;
}
cout << cnt << "\n";
}
int main() {
freopen("viecnha.inp", "r", stdin);
freopen("viecnha.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T >> C;
t.resize(C);
for (int i = 0; i < C; i++) cin >> t[i];
if (C <= 20) sub1(); // it viec: vet can 2^C
else sub2(); // nhieu viec: tham lam
return 0;
}
Bình luận