Hướng dẫn giải của Đặt phòng
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 ~k~ khách có số tiền đặt cọc lớn nhất; nếu bằng tiền thì ưu tiên khách đặt sớm hơn (chỉ số nhỏ hơn). Kết quả in theo thứ tự tăng dần.
Sub 1: Chọn lần lượt — ~O(n \cdot k)~, dùng khi ~n \le 1000~
Lặp ~k~ lần, mỗi lần chọn khách chưa được chọn có tiền lớn nhất (khi bằng nhau, lấy chỉ số nhỏ hơn).
Nếu chỉ nộp sub này: đúng 9/10 test.
Sub 2: Sắp xếp — ~O(n \log n)~
Sắp xếp các khách theo tiền giảm dần, cùng tiền thì chỉ số tăng dần. Lấy ~k~ khách đầu, sắp lại chỉ số rồi in.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Dữ liệu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<long long> a; // a[1..n]: so tien dat coc cua khach i
// Sub 1: vet can O(n*k). Moi buoc chon khach co coc lon nhat chua duoc chon;
// neu hai khach bang tien thi chon nguoi dat coc som hon (chi so nho hon). Dung khi n <= 1000.
void sub1() {
vector<bool> chosen(n + 1, false);
for (int t = 0; t < k; t++) {
int best = 0;
for (int i = 1; i <= n; i++)
if (!chosen[i] && (best == 0 || a[i] > a[best])) best = i;
chosen[best] = true;
}
for (int i = 1; i <= n; i++)
if (chosen[i]) cout << i << " ";
cout << "\n";
}
// Sub 2: sap xep cac khach theo (tien giam dan, chi so tang dan), lay k khach dau,
// roi sap xep lai chi so de in tang dan. O(n log n).
void sub2() {
vector<int> idx(n);
for (int i = 0; i < n; i++) idx[i] = i + 1;
sort(idx.begin(), idx.end(), [&](int x, int y) {
if (a[x] != a[y]) return a[x] > a[y];
return x < y;
});
vector<int> pick(idx.begin(), idx.begin() + k);
sort(pick.begin(), pick.end());
for (int x : pick) cout << x << " ";
cout << "\n";
}
int main() {
cin >> n >> k;
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận