Hướng dẫn giải của [200 đề thầy Đức] Bài 87: Kiến di chuyển
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
Ba con kiến không vượt qua nhau khi cần thiết, nên ta sắp xếp vị trí ban đầu. Mỗi giây đúng một con kiến đi một bước, nên số giây tối thiểu bằng tổng quãng đường tối thiểu để đạt khoảng cách ≥ d giữa mọi cặp.
Sub 1: Vét cạn vị trí cuối — ~O(W^3)~
Thử mọi bộ vị trí cuối (y1, y2, y3) trong một khoảng quanh các vị trí ban đầu, chọn bộ có khoảng cách mọi cặp ≥ d và tổng quãng đường nhỏ nhất. Đạt 2/21 test, còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
long long x[3], d;
cin >> x[0] >> x[1] >> x[2] >> d;
long long lo = min({x[0], x[1], x[2]}) - 2 * d - 2;
long long hi = max({x[0], x[1], x[2]}) + 2 * d + 2;
// Vét cạn: thử mọi bộ vị trí cuối (y1, y2, y3) trong khoảng [lo, hi]
long long best = LLONG_MAX;
for (long long y1 = lo; y1 <= hi; y1++)
for (long long y2 = lo; y2 <= hi; y2++) {
if (llabs(y1 - y2) < d) continue;
for (long long y3 = lo; y3 <= hi; y3++) {
if (llabs(y1 - y3) < d || llabs(y2 - y3) < d) continue;
// tổng số giây = tổng quãng đường mỗi kiến phải đi
long long cost = llabs(y1 - x[0]) + llabs(y2 - x[1]) + llabs(y3 - x[2]);
best = min(best, cost);
}
}
cout << best << "\n";
}
return 0;
}
Sub 2: Đưa về bài đơn điệu — ~O(q)~
Sắp xếp x1 ≤ x2 ≤ x3, đặt t = (x1, x2 - d, x3 - 2d). Khi đó bài toán thành tìm dãy w không giảm gần t nhất về tổng |wi - ti|. Nghiệm tối ưu lấy giá trị trong tập {t1, t2, t3}, nên thử 27 tổ hợp. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
long long x[3], d;
cin >> x[0] >> x[1] >> x[2] >> d;
sort(x, x + 3); // kiến không cần vượt nhau: giữ nguyên thứ tự trái-phải
// Đưa bài về bài toán "không giảm": nếu vị trí cuối là y1 < y2 < y3
// với y2 - y1 >= d, y3 - y2 >= d, đặt w1 = y1, w2 = y2 - d, w3 = y3 - 2d
// thì w1 <= w2 <= w3, và chi phí = sum |w_i - t_i| với t = (x1, x2 - d, x3 - 2d)
long long t[3] = {x[0], x[1] - d, x[2] - 2 * d};
// Nghiệm tối ưu của bài này luôn lấy giá trị w_i thuộc tập {t_1, t_2, t_3}
long long best = LLONG_MAX;
for (int a = 0; a < 3; a++)
for (int b = 0; b < 3; b++)
for (int c = 0; c < 3; c++) {
long long w1 = t[a], w2 = t[b], w3 = t[c];
if (!(w1 <= w2 && w2 <= w3)) continue;
long long cost = llabs(w1 - t[0]) + llabs(w2 - t[1]) + llabs(w3 - t[2]);
best = min(best, cost);
}
cout << best << "\n";
}
return 0;
}
Bình luận