Solutions of Three sequences

Select solution language

hungkm466 Created at 2 likes

## 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; }$