解題區/解題區 - 其他題目

BZOJ 1047 [HAOI2007] 理想的正方形

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

題目連結

在一個 $N \times M$ 的矩形中，找到一個 $K \times K$ 的正方形區域，求所有正方形區域中最大值減去最小值的差最小為何。

Sample Input

1
2
3
4
5
6
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2

Sample Output

1
1

Solution

明顯地是一個滑動窗口，對於一維情況很明顯地直接套用單調隊列即可。

對於二維的滑動窗口，則可以對每一列維護一個 列 的單調隊列，對於某一行掃描時，再維護一個 行 的單調隊列，往右移動窗口時，把移動到 列 的單調隊列的極值加入，並且把超出窗口的列的極值移除。

由上至下、由左而右掃描每一行上的元素，找到以此元素為正方形右下角的正方形區域最大最小值。時間複雜度 $O(N^2)$，怕重複的代碼太多，直接寫成模板搭配 std::deque<> 來使用，但這樣的寫法會比純數組來得慢 (method interface 和 cache 的影響 …)。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 1024;
template<typename WTYPE, bool FUNC(WTYPE, WTYPE)>
class MonoQueue {
public:
    deque< pair<int, WTYPE> > Q;
    int K;
    void setWindow(int K) {
        this->K = K;
    }
    inline void add(int idx, WTYPE val) {
        while (!Q.empty() && Q.front().first <= idx - K)
            Q.pop_front();
        while (!Q.empty() && FUNC(val, Q.back().second))
            Q.pop_back();
        Q.push_back({idx, val});
    }
    inline pair<int, WTYPE> top() {
        return Q.front();
    }
};
bool cmp1(int a, int b) { return a > b; }
bool cmp2(int a, int b) { return a < b; }
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = readchar()) < '-')    {if(c == EOF) return 0;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = readchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int N, M, K, val;
    while (ReadInt(&N)) {
        ReadInt(&M);
        ReadInt(&K);
                
        MonoQueue<int, cmp1> mxC[MAXN];
        MonoQueue<int, cmp2> mnC[MAXN];
        for (int i = 0; i < M; i++)
            mxC[i].setWindow(K), mnC[i].setWindow(K);
        int ret = INT_MAX;
        
        for (int i = 0; i < N; i++) {
            MonoQueue<int, cmp1> mxR;
            MonoQueue<int, cmp2> mnR;
            mxR.setWindow(K), mnR.setWindow(K);
            for (int j = 0; j < M; j++) {
                ReadInt(&val);				
                mxC[j].add(i, val);
                mxR.add(j, mxC[j].top().second);
                
                mnC[j].add(i, val);
                mnR.add(j, mnC[j].top().second);
                
                if (i >= K-1 && j >= K-1)
                    ret = min(ret, mxR.top().second - mnR.top().second);
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}