## 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;
}
```
hungkm466
Created at
0 likes