P2216. 理想的正方形

发表于 分类于 阅读次数： Waline： 本文字数： 338 阅读时长 ≈ 1 分钟

考点

  • 单调队列

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50;
int n, m, k, a[maxn][maxn];
int row_mx[maxn][maxn], row_mi[maxn][maxn];
int col_mx[maxn][maxn], col_mi[maxn][maxn];
int h_mx, t_mx, q_mx[maxn];
int h_mi, t_mi, q_mi[maxn];

int main() {
  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    h_mx = t_mx = h_mi = t_mi = 0;
    for (int j = 1; j <= m; ++j) {
      // 每行k单位的最大值
      while (h_mx < t_mx && j - q_mx[h_mx] >= k) ++h_mx;
      while (h_mx < t_mx && a[i][q_mx[t_mx - 1]] <= a[i][j]) --t_mx;
      q_mx[t_mx++] = j;
      if (j >= k) row_mx[i][j - k + 1] = a[i][q_mx[h_mx]];
      // 每行k单位的最小值
      while (h_mi < t_mi && j - q_mi[h_mi] >= k) ++h_mi;
      while (h_mi < t_mi && a[i][q_mi[t_mi - 1]] >= a[i][j]) --t_mi;
      q_mi[t_mi++] = j;
      if (j >= k) row_mi[i][j - k + 1] = a[i][q_mi[h_mi]];
    }
  }
  for (int j = 1; j <= m - k + 1; ++j) {
    h_mx = t_mx = h_mi = t_mi = 0;
    for (int i = 1; i <= n; ++i) {
      // 每列k单位的最大值
      while (h_mx < t_mx && i - q_mx[h_mx] >= k) ++h_mx;
      while (h_mx < t_mx && row_mx[q_mx[t_mx - 1]][j] <= row_mx[i][j]) --t_mx;
      q_mx[t_mx++] = i;
      if (i >= k) col_mx[i - k + 1][j] = row_mx[q_mx[h_mx]][j];
      // 每列k单位的最小值
      while (h_mi < t_mi && i - q_mi[h_mi] >= k) ++h_mi;
      while (h_mi < t_mi && row_mi[q_mi[t_mi - 1]][j] >= row_mi[i][j]) --t_mi;
      q_mi[t_mi++] = i;
      if (i >= k) col_mi[i - k + 1][j] = row_mi[q_mi[h_mi]][j];
    }
  }
  int ans = 0x3f3f3f3f;
  for (int i = 1; i <= n - k + 1; ++i) {
    for (int j = 1; j <= m - k + 1; ++j) {
      ans = min(ans, col_mx[i][j] - col_mi[i][j]);
    }
  }
  cout << ans;
  return 0;
}

思路

直接上《深进》