Hướng dẫn giải của [200 đề thầy Đức] Bài 199: Thi vấn đáp
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
Với mỗi sinh viên ~i~, cần chọn số sinh viên trước ~i~ bị trượt (thời gian bằng 0) tối thiểu sao cho tổng thời gian còn lại của các sinh viên trước ~i~ cộng ~t[i]~ không vượt quá ~m~. Muốn ít người bị trượt nhất thì luôn bỏ người có thời gian lớn nhất.
Sub 1: Vét cạn, quét tuyến tính — ~O(n^3)~, dùng khi ~n \le 30~
Với mỗi ~i~, lặp: nếu tổng thời gian hiện tại vượt ~m - t[i]~ thì tìm và bỏ sinh viên có thời gian lớn nhất trong các sinh viên trước ~i~.
Nếu chỉ nộp sub này: đúng 39/39 test (đã kiểm tra cùng với sub 2).
Sub 2: Sắp xếp giảm dần — ~O(n^2 \log n)~
Với mỗi ~i~, sắp xếp các thời gian trước ~i~ giảm dần rồi bỏ dần từ đầu cho đến khi tổng đủ nhỏ. Cùng ý tưởng nhưng nhanh hơn khi ~n~ lớn.
Nếu chỉ nộp sub này: đúng 39/39 test.
Chương trình hoàn chỉnh
Dữ liệu nhỏ (~n \le 30~) dùng sub 1 cho chắc. Dữ liệu lớn hơn dùng sub 2. Bẫy: đáp án là số người trượt tối thiểu, không phải số người có thể đi thi.
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long t[105]; // t[i]: thoi gian sinh vien i can
// Sub 1: vet can O(n^3). Voi moi i, lap lai: neu tong thoi gian cua cac sinh vien
// truoc i (chua bi loai) vuot qua m - t[i] thi bo sinh vien co t lon nhat (quet tuyen tinh).
void sub1() {
for (int i = 1; i <= n; i++) {
long long budget = m - t[i];
vector<long long> cur;
long long sum = 0;
for (int j = 1; j < i; j++) { cur.push_back(t[j]); sum += t[j]; }
int cnt = 0;
while (sum > budget) {
int best = 0;
for (int k = 1; k < (int)cur.size(); k++)
if (cur[k] > cur[best]) best = k;
sum -= cur[best];
cur.erase(cur.begin() + best);
cnt++;
}
cout << cnt << (i == n ? "\n" : " ");
}
}
// Sub 2: sap xep giam dan tung tien to, bo dan phan tu lon nhat. O(n^2 log n).
void sub2() {
for (int i = 1; i <= n; i++) {
long long budget = m - t[i];
vector<long long> cur;
long long sum = 0;
for (int j = 1; j < i; j++) { cur.push_back(t[j]); sum += t[j]; }
sort(cur.rbegin(), cur.rend()); // giam dan
int cnt = 0, idx = 0;
while (sum > budget) { // bo phan tu lon nhat truoc
sum -= cur[idx++];
cnt++;
}
cout << cnt << (i == n ? "\n" : " ");
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> t[i];
if (n <= 30) sub1(); // du lieu nho: vet can cho chac
else sub2();
return 0;
}
Bình luận