Hướng dẫn giải của Giờ sinh hoạt (KS THCS 04)
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
Mỗi xe chở tối đa 2 người và tổng trọng lượng không quá ~x~. Cần ghép người để số xe ít nhất. Ý tưởng: sắp xếp, rồi ghép người nhẹ nhất với người nặng nhất khi ghép được.
Sub 1: Tham lam O(n^2) — ~O(n^2)~, dùng khi ~n \le 2000~
Lấy người nhẹ nhất chưa xếp, tìm người nặng nhất còn lại có thể đi cùng, nếu không có thì đi một mình. Nếu chỉ nộp sub này: đúng 15/20 test.
Sub 2: Hai con trỏ — ~O(n \log n)~
Sau khi sắp xếp dùng hai con trỏ ~i~ (nhẹ nhất) và ~j~ (nặng nhất). Nếu ~a_i + a_j \le x~ thì ghép và tăng ~i~; luôn giảm ~j~ và tăng số xe. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~n \le 2000~ dùng sub 1, còn lại dùng sub 2. 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;
int n;
long long X; // suc chua cua moi xe
vector<long long> a; // trong luong (da sap xep tang dan)
// Sub 1: tham lam O(n^2). Lay nguoi nhe nhat chua di, ghep voi nguoi nang nhat co the di cung.
void sub1() {
vector<bool> used(n, false);
int cnt = 0;
for (int i = 0; i < n; i++) {
if (used[i]) continue;
used[i] = true;
for (int j = n - 1; j > i; j--)
if (!used[j] && a[i] + a[j] <= X) { used[j] = true; break; }
cnt++;
}
cout << cnt << "\n";
}
// Sub 2: hai con tro O(n log n). Nguoi nhe nhat (i) di chung voi nguoi nang nhat (j) neu duoc.
void sub2() {
int i = 0, j = n - 1, cnt = 0;
while (i <= j) {
if (i < j && a[i] + a[j] <= X) i++;
j--;
cnt++;
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> X;
a.assign(n, 0);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
if (n <= 2000) sub1();
else sub2();
return 0;
}
Bình luận