## Hướng dẫn
Các bạn nên làm bài [Ba dãy](https://marisaoj.com/problem/507) trước để hiểu tư tưởng của thuật toán: Tăng vị trí của phần tử nhỏ nhất trong các phần tử được chọn lên 1 đơn vị.\
Mục đích là làm cho khoảng cách giữa các phần tử trên trục số là nhỏ nhất. Từ đó có thể dễ dàng tìm được giá trị tối ưu của bài toán.
Code:
```
#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 maximize(X &x, const Y &y){return (x < y) ? x = y, 1 : 0;}
template<class X, class Y>
bool minimize(X &x, const Y &y){return (x > y) ? x = y, 1 : 0;}
const int MAXN = 1e3 + 5;
int n,m;
int a[MAXN][MAXN];
int pos[MAXN];
signed main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
FOR(i,1,n)
{
pos[i] = 1;
FOR(j,1,m) cin >> a[i][j];
}
FOR(i,1,n) sort(a[i]+1, a[i]+m+1);
int res = 2e9, mx, mn, cur;
while (1)
{
mx = -2e9, mn = 2e9, cur = 1;
FOR(i,1,n)
{
maximize(mx, a[i][pos[i]]);
if (minimize(mn, a[i][pos[i]])) cur = i;
}
minimize(res, mx - mn);
if (++pos[cur] > m) break;
}
cout << res;
return 0;
}
```
## KHUYÊN CÁC BẠN NÊN SUY NGHĨ TRƯỚC KHI ĐỌC SOLUTION NHAA
Bài này nằm trong mức 2 và độ khó chỉ có 1200 nên mình nghĩ Segment Tree hơi lố. Vì vậy bạn
có thể tự động não tìm cách tối ưu đơn giản hơn nhé
## Ý tưởng
Bài này chúng ta sẽ sử dụng lại ý tưởng của bài [Ba dãy](https://marisaoj.com/problem/507). Trong bài ba dãy ta sắp xếp lại các dãy
tăng dần và ta sẽ bắt đầu chọn từ những phần tử nhỏ nhất. Cập nhật biến trả lời và tăng vị trí phần
tử nhỏ nhất trong các phần tử được chọn lên 1.
Trong bài này ta sẽ mở rộng ra để quản lý nhiều dòng, và cập nhật biến trả lời là khoảng cách giữa
max và min trong các phần tử được chọn
## Hướng giải
Ta dùng một mảng pos để lưu vị trí đang xét của mỗi dòng, tất cả bắt đầu xét từ 1. Trong mỗi lần
duyệt ta tìm phần tử được chọn có giá trị max và min, cập nhật res = min(res, max - min) và tăng
pos của dòng chứa phần tử min lên 1.
Có thể thấy trong trường hợp tệ nhất sẽ phải duyệt qua tất cả các phần tử **O(n * m)** và mỗi lần cập
nhật sẽ phải tốn **O(n)** để tìm phần tử max và min dẫn đến độ phức tạp **O(n * (n * m))** => **TLE**.
Đến đây ta sẽ cần tìm cách lấy được dòng max và min nhanh chóng. Mình nghĩ sẽ có nhiều cách
để làm điều này nhưng **riêng mình** thì dùng _Segment tree_ vì đã quen :)
Với Segment tree thì ta có thể dễ dàng truy vấn và cập nhật dòng có phần tử max và min trong thời
gian **O(log(n))**
Vậy ta có thể giải quyết bài này với độ phức tạp **O(n*m\*log(n))**
## Code
```
/*
"Dùng Segment thật hả?!"
- KevinPhan 18/06/2025 -
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int a[1009][1009], pos[1009];
pair<int, int> seg_tree[4009];
pair<int, int> comp(pair<int, int> x, pair<int, int> y)
{
pair<int, int> ret;
if (x.first == -1) ret.first = y.first;
else if (y.first == -1) ret.first = x.first;
else if (a[x.first][pos[x.first]] >= a[y.first][pos[y.first]]) ret.first = x.first;
else ret.first = y.first;
if (x.second == -1) ret.second = y.second;
else if (y.second == -1) ret.second = x.second;
else if (a[x.second][pos[x.second]] <= a[y.second][pos[y.second]]) ret.second = x.second;
else ret.second = y.second;
return ret;
}
void build(int id, int l, int r)
{
if (l == r)
{
seg_tree[id] = {l, l};
return;
}
int mid = l + (r - l) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
seg_tree[id] = comp(seg_tree[id * 2], seg_tree[id * 2 + 1]);
}
void update(int id, int l, int r, int pos, int k)
{
if (l == r && l == pos)
{
seg_tree[id] = {k, k};
return;
}
int mid = l + (r - l) / 2;
if (pos <= mid) update(id * 2, l, mid, pos, k);
else update(id * 2 + 1, mid + 1, r, pos, k);
seg_tree[id] = comp(seg_tree[id * 2], seg_tree[id * 2 + 1]);
}
pair<int, int> query(int id, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr) return seg_tree[id];
if (l > qr || r < ql) return {-1, -1};
int mid = l + (r - l) / 2;
return comp(query(id * 2, l, mid, ql, qr), query(id * 2 + 1, mid + 1, r, ql, qr));
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
sort(a[i] + 1, a[i] + m + 1);
pos[i] = 1;
}
build(1, 1, n);
int res = INT_MAX;
while (true)
{
pair<int, int> cur = query(1, 1, n, 1, n);
//cout << cur.first << ' ' << cur.second << '\n';
res = min(res, a[cur.first][pos[cur.first]] - a[cur.second][pos[cur.second]]);
pos[cur.second]++;
if (pos[cur.second] > m) break;
//update chi mang tinh chat day len gia tri min va max chu khong thay doi id
update(1, 1, n, cur.second, cur.second);
}
cout << res;
return 0;
}
```
hungkm466
Created at
4 likes
kevinPhan
Created at
0 likes