Minima/maxima over all fixed-size arrays (multi-dimensional)

http://codeforces.com/blog/entry/53810

$N\cdot M$크기의 2차원 배열이 있다고 생각해 보자.
이 배열의 $A\cdot B$크기의 부분배열의 최솟값/최댓값을 구하는 방법이다.

바로 solution을 말하자면 1차원 배열일때의 solution을 2차원으로 확장 시키는 것이다.

1차원일 경우에는 sweeping방법으로 훑으면서 greedy하게 답을 구해낼 수 있다.
$i < j, A[i] >= A[j]$이면 $A[i]$를 삭제하면 된다.
(물론 원하는 부분배열의 크기보다 크거나 같은 경우일때 삭제시킨다.)

2차원일때는 위의 방법을 가지고 y축으로 한번 해서 압축, x축으로 해서 압축하면 나온다.

#include <cstdio> #include <algorithm> #include <vector> #include <set> std::multiset<int> save; int N, M, A, B; int map[1001][1001]; int tmp[1001][1001], ret[1001][1001]; int main() {     scanf("%d%d%d%d", &N, &M, &A, &B);     for (int n = 1;n <= N;n++)         for (int m = 1;m <= M;m++)             scanf("%d", &map[n][m]);     //세로 압축     for (int m = 1;m <= M;m++) {         save.clear();         // 일단 크기가 A되기전 까지 집어넣음         for (int n = 1;n < A;n++) save.insert(-map[n][m]);             for (int n = A;n <= N;n++) {             save.insert(-map[n][m]);             // 크기가 A가 넘으면 앞에 들어왔던것 지움             if (save.size() > A) save.erase(save.find(-map[n - A][m]));             tmp[n - A + 1][m] = -*save.begin();         }     }     //가로 압축     for (int n = 1;n <= N;n++) {         save.clear();         //일단 크기가 B되기전 까지 집어넣음         for (int m = 1;m < B;m++) save.insert(-tmp[n][m]);         for (int m = B;m <= M;m++) {             save.insert(-tmp[n][m]);             //크기가 B가 넘으면 앞에 들어왔던것 지움             if (save.size() > B) save.erase(save.find(-tmp[n][m - B]));             ret[n][m - B + 1] = -*save.begin();         }     }     printf("\n압축 후\n");     for (int n = 1;n <= N - A + 1;n++) {         for (int m = 1;m <= M - B + 1;m++)             printf("%d ", ret[n][m]);         printf("\n");     }     return 0; } Colored by Color Scripter

cs

위의 소스는 2차원 배열일때 $O(N\cdot M)$복잡도로 maximum을 구하는 방법이다.

minimum을 구하고 싶으면 multiset에 -붙은것을 다 없애면 된다.