## Hướng dẫn
- Nhận thấy để |A[i] - B[j]| + |B[j] - C[k]| + |C[k] - A[i]| đạt nhỏ nhất thì khoảng cách giữa A[i], B[j], C[k] trên trục số phải nhỏ nhất hay vị trí giữa chúng phải gần nhau nhất.
Bài này ta sẽ sử dụng kĩ thuật **"Ba" con trỏ**.\
Để thuận tiện cho việc duyệt từng phần tử và tìm giá trị tối ưu.\
Đặt i = 1, j = 1, k = 1 (1 ≤ i, j, k ≤ n).
Với mỗi lần lặp, tăng vị trí của phần tử nhỏ nhất lên 1 đơn vị.
Code: O(3n)
```
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=a; i<=b; ++i)
template<class X, class Y>
bool minimize(X &x, const Y &y){return (x > y) ? x = y, 1 : 0;}
const int MAXN = 1e5 + 5;
int n;
int a[MAXN], b[MAXN], c[MAXN];
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
FOR(i,1,n) cin >> a[i];
FOR(i,1,n) cin >> b[i];
FOR(i,1,n) cin >> c[i];
sort(a+1,a+n+1);
sort(b+1,b+n+1);
sort(c+1,c+n+1);
int res = INT_MAX;
for (int i=1, j=1, k=1; i<=n && j<=n && k<=n; )
{
int cur = abs(a[i] - b[j]) + abs(b[j] - c[k]) + abs(c[k] - a[i]);
minimize(res, cur);
if (a[i] <= b[j] && a[i] <= c[k]) ++i;
else if (b[j] <= a[i] && b[j] <= c[k]) ++j;
else ++k;
}
cout << res;
return 0;
}
```
hungkm466
Created at
0 likes