題目描述
有一個 \(a \times b\) 的整陣列成的矩陣，現請你從中找出一個 \(n \times n\) 的正方形區域，使得該區域所有數中的最大值和最小值的差最小，
輸入格式
第一行為 \(3\) 個整數，分別表示 \(a,b,n\) 的值，
第二行至第 \(a+1\) 行每行為 \(b\) 個非負整數，表示矩陣中相應位置上的數，每行相鄰兩數之間用一空格分隔，
輸出格式
僅一個整數，為 \(a \times b\) 矩陣中所有“ \(n \times n\) 正方形區域中的最大整數和最小整數的差值”的最小值，
輸入輸出樣例
輸入 #1
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
輸出 #1
1
說明/提示
問題規模，
矩陣中的所有數都不超過 \(1,000,000,000\)，
\(20\%\) 的資料 \(2 \le a,b \le 100,n \le a,n \le b,n \le 10\)，
\(100\%\) 的資料 \(2 \le a,b \le 1000,n \le a,n \le b,n \le 100\)，
代碼展示
一看就是單調佇列
#include <iostream>
#include <deque>
using namespace std;
const int N = 1024;
int G[N][N];
deque<pair<int, int>> _maxn;
deque<pair<int, int>> _minn;
int maxn[N][N];
int minn[N][N];
int maxn2[N][N];
int minn2[N][N];
int ans_max[N][N];
int ans_min[N][N];
int main()
{
int a, b, n;
cin >> a >> b >> n;
for (int i = 1; i <= a; i++)
{
for (int j = 1; j <= b; j++)
{
cin >> G[i][j];
}
}
for (int i = 1; i <= a; i++)
{
for (int j = 1; j <= b; j++)
{
while (!_maxn.empty() && _maxn.front().second <= j - n)
_maxn.pop_front();
while (!_minn.empty() && _minn.front().second <= j - n)
_minn.pop_front();
while (!_maxn.empty() && _maxn.back().first < G[i][j])
_maxn.pop_back();
while (!_minn.empty() && _minn.back().first > G[i][j])
_minn.pop_back();
_maxn.push_back(make_pair(G[i][j], j));
_minn.push_back(make_pair(G[i][j], j));
if (j >= n)
{
maxn[i][j] = _maxn.front().first;
minn[i][j] = _minn.front().first;
}
}
_maxn.clear();
_minn.clear();
}
for (int i = n; i <= b; i++)
{
for (int j = 1; j <= a; j++)
{
while (!_maxn.empty() && _maxn.front().second <= j - n)
_maxn.pop_front();
while (!_minn.empty() && _minn.front().second <= j - n)
_minn.pop_front();
while (!_maxn.empty() && _maxn.back().first < maxn[j][i])
_maxn.pop_back();
while (!_minn.empty() && _minn.back().first > minn[j][i])
_minn.pop_back();
_maxn.push_back(make_pair(maxn[j][i], j));
_minn.push_back(make_pair(minn[j][i], j));
if (j >= n)
{
ans_max[j][i] = _maxn.front().first;
ans_min[j][i] = _minn.front().first;
}
}
_maxn.clear();
_minn.clear();
}
int ans = 0x3f3f3f3f;
for (int i = n; i <= a; i++)
for (int j = n; j <= b; j++)
ans = min(ans, ans_max[i][j] - ans_min[i][j]);
cout << ans;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298798.html
標籤：其他