Hướng dẫn giải của [CSES 1091] Concert Tickets
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.
Ta thêm tất cả các giá vé vào một multiset, sau đó ta có thể tìm và xóa hiệu quả giá vé tương ứng với giá mà khách hàng đưa ra.
Vì ta cần tìm giá vé lớn nhất không vượt quá giá đã đưa ra, ta sử dụng hàm upper_bound để tìm giá vé nhỏ nhất lớn hơn giá đã đưa ra. Sau đó, ta giảm iterator đi một để tìm giá vé mong muốn, rồi xóa nó.
Nếu iterator ban đầu trỏ tới giá vé nhỏ nhất, tức là tất cả các giá vé đều lớn hơn giá đã đưa ra và ta không thể đưa vé cho khách hàng đó.
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
multiset<int> prices;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
prices.insert(x);
}
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
auto it = prices.upper_bound(x);
if (it == prices.begin()) {
cout << "-1\n";
} else {
it--;
cout << *it << "\n";
prices.erase(it);
}
}
}
Chương trình tham khảo
#include <iostream>
#include <set>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
multiset<int> prices;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
prices.insert(x);
}
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
auto it = prices.upper_bound(x);
if (it == prices.begin()) {
cout << "-1\n";
} else {
it--;
cout << *it << "\n";
prices.erase(it);
}
}
}
Bình luận