Hướng dẫn giải của Người lái thuyền (KS2)
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
Bình phải đi từ 0 đến M, đón người ở s rồi trả ở t. Người có s < t chỉ cần đi qua một lần. Người có s > t phải đi tới s rồi quay lại t, nên các đoạn trong [t, s] phải đi qua 3 lần. Đáp án là ~M + 2 \cdot (độ dài hợp các đoạn [t, s] của người đi lùi)~.
Sub 1: vét cạn theo đoạn đơn vị — ~O(N \cdot M)~, dùng khi ~N \cdot M \le 10^7~
Đánh dấu từng đoạn đơn vị ~[x, x+1]~ nằm trong đoạn đi lùi của một người, rồi đếm. Nếu chỉ nộp sub này: đúng 20/25 test.
Sub 2: gộp đoạn — ~O(N \log N)~
Sắp xếp các đoạn ~[t, s]~ của người đi lùi, gộp các đoạn giao nhau rồi cộng độ dài. Đây là lời giải đầy đủ, đúng 25/25 test. Đáp án có thể lớn, nên dùng long long.
Chương trình hoàn chỉnh
main đọc N, M và các cặp (s, t). Nếu ~N \cdot M \le 10^7~ thì gọi sub1, ngược lại gọi sub2. 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;
long long n, m;
long long S[300005], T[300005]; // người thứ i đi từ S[i] đến T[i]
// Sub 1: vét cạn theo từng đoạn đơn vị [x, x+1] của sông (dùng khi n*m nhỏ).
// Đoạn nào nằm trong một hành trình đi lùi (S > T) thì phải đi qua 3 lần.
void sub1() {
vector<char> cov(m, 0);
for (int i = 1; i <= n; i++)
if (S[i] > T[i])
for (long long x = T[i]; x < S[i]; x++) cov[x] = 1;
long long cnt = 0;
for (long long x = 0; x < m; x++) cnt += cov[x];
cout << m + 2 * cnt << "\n";
}
// Sub 2: gộp các đoạn [T, S] của những người đi lùi, O(n log n).
// Đáp án = M + 2 * (độ dài hợp các đoạn đi lùi).
void sub2() {
vector<pair<long long, long long>> v;
for (int i = 1; i <= n; i++)
if (S[i] > T[i]) v.push_back({T[i], S[i]});
sort(v.begin(), v.end());
long long len = 0, cl = 0, cr = 0;
bool has = false;
for (auto &p : v) {
if (!has) { cl = p.first; cr = p.second; has = true; }
else if (p.first <= cr) cr = max(cr, p.second);
else { len += cr - cl; cl = p.first; cr = p.second; }
}
if (has) len += cr - cl;
cout << m + 2 * len << "\n";
}
int main() {
freopen("VILLAGES.inp", "r", stdin);
freopen("VILLAGES.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> S[i] >> T[i];
if (n * m <= 10000000LL) sub1();
else sub2();
return 0;
}
Bình luận