## 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;
}
```
###**ĐÂY LÀ $1$ HƯỚNG KHÁC CHUYỂN TỪ $3$ CON TRỎ VỀ $2$ CON TRỎ.**<br>
**HINT:** Cố gắng chuyển từ tính $3$ giá trị $i,j,k$ về $2$ giá trị. Chú ý biểu thức cần tìm giá trị nhỏ nhất có dạng $|a-b|+|b-c|+|c-a|$<br>
#**HƯỚNG DẪN:**
-Xét dạng của biểu thức: $|a-b|+|b-c|+|c-a|$<br>
+ Có $|a-b|=|b-a|$ do đó vai trò $a,b,c$ như nhau(đổi chỗ cho nhau, biểu thức cũng không thay đổi.)
Do đó có thể giả sử $a>=b>=c$ hay $a<=b<=c$ đều như nhau. Khi đó biểu thức phá dấu giá trị tuyệt đối trở thành:
$a-b+b-c+a-c=2\*(a-c)$ (loại được $b$)<br>
- Mục tiêu của ta là tìm các cặp $a,c$ để tồn tại $1$ phần tử $b$ ở giữa hay với mỗi $b,$ ta tìm các phần tử $a<=b,c>=b$ gần nhất(để khoảng cách $a,c$ nhỏ nhất)(xuất phát gốc từ $b,$ tìm $a,c$ sẽ dễ hơn là tìm $a,c$ sao cho có phần tử $b$ ở giữa.<br>
- Tạo $1$ hàm $timmin(int a[],int b[],int c[])$ có ý nghĩa tìm $i,j,k$ sao cho $ai<=bj<=ck$ và biểu thức $|a-b|+|b-c|+|c-a|$ nhỏ nhất.<br>
- Chạy $j$ tăng dần của mảng $b.$ Với mỗi $j,$ ta tìm $i$ nhỏ nhất sao cho $ai>bj,k$ nhỏ nhất sao cho $bj<=ck.$(hai con trỏ)
##**CODE MẪU:**
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[100005],b[100005],c[100005];
int timmin(int a[],int b[],int c[])
{
int ja=0,jc=0,ans=2e9;
for(int i=0;i<n;i++)
{
while(ja<n)
{
if(a[ja]<=b[i]) ja++;//dg lay cai lon hon ma index nho nhat.-> phai cho > -> -1 se ve <=(de xly)
else break;
}
while(jc<n)
{
if(c[jc]<b[i]) jc++;//= thi phai lay.
else break;
}
if(ja==0||jc==n) continue;
else
{
ans=min(ans,2*(c[jc]-a[ja-1]));
}
}
//cout<<ans<<endl;
return ans;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) cin>>c[i];
sort(a,a+n);sort(b,b+n);sort(c,c+n);
cout<<min(timmin(a,b,c),min(timmin(a,c,b),min(timmin(c,a,b),min(timmin(c,b,a),min(timmin(b,c,a),timmin(b,a,c))))));
}
```
<br>
- **Chú ý** nếu $i=0, k=n$ tức là không có $ai,ck$ sao cho $ai<=bj, ck>bj.$<br>
- **Chú ý** phải xét đủ các trường hợp phần tử mảng $a,b,c$ nằm giữa.<br>
hungkm466
Created at
14 likes
sharinganvanhoadong
Created at
0 likes