Hướng dẫn giải của [CSES 1629] Movie Festival
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.
Một phương án tối ưu là luôn chọn một bộ phim bắt đầu sau bộ phim cuối cùng ta đã xem và có thời gian kết thúc sớm nhất trong tất cả các bộ phim như vậy. Điều này có thể thực hiện bằng cách sắp xếp các bộ phim theo thời gian kết thúc, sau đó duyệt qua chúng và chọn một cách tham lam bộ phim tiếp theo.
Thuật toán hoạt động đúng vì việc chọn bộ phim tiếp theo có thời gian kết thúc sớm nhất luôn là an toàn. Nếu ta chọn một bộ phim khác, nó sẽ kết thúc muộn hơn và hạn chế nhiều hơn các lựa chọn trong tương lai.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> movies;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
movies.emplace_back(b, a);
}
sort(movies.begin(), movies.end());
int count = 0;
int end = 0;
for (auto [b, a] : movies) {
if (a >= end) {
end = b;
count++;
}
}
cout << count << "\n";
}
Chương trình tham khảo
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> movies;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
movies.emplace_back(b, a);
}
sort(movies.begin(), movies.end());
int count = 0;
int end = 0;
for (auto [b, a] : movies) {
if (a >= end) {
end = b;
count++;
}
}
cout << count << "\n";
}
Bình luận