题解 P2716 【和谐的雪花】

· · 题解

看了楼下的几个题解，好像都用的是动归，我提供个非动归的思想，效率可以达到O(nm*logn)，测试点总共用时600ms(未开O2）。

在阐述题解之前，先普及个知识：滑动窗口算法。

作用：若有一个序列A1, A2, ... , An，其中存在着若干个长度为k的子序列（连续的k个元素），事实上存在着n-k+1个子序列。我们想求这些子序列之中的最大（小）值，可以采取滑动窗口算法，复杂度为O(n)。

思想：假设存在一个序列A={3, 2, 4, 6, 5, 9, 8, 1}，k=3时，B[i]记录A[i-k+1]到A[i]的最大值（先谈一个）。这个问题可以看成：有一个长度为k的队列，每次弹出一个数，进入一个数，并维护这个队列的最大值。怎么维护呢？在A序列中，3在2的左边。这意味着，2在3离开队列前，一直会被3“压迫”着，不会成为队列的最大值，只有在3出队时才有可能成为最大值。之后，4入队。此时无论如何，前面的3永远不会成为最大值了（包括2），换句话说，此时3和2是无用的，可以删除。当删除无用元素后，此时，滑动窗口中的有用元素是递减的。我们把这些有用的元素看成一个队列（事实上，可以用一个队列Q单独保存其有用元素对应的下标。这个队列对应的元素是单调队列）。每次维护，分成3个步骤：

1.如果Q队列非空（只会出现第一次未入队）且Q队头下标已经不在子序列的区间中，出队；

2.如果Q队列非空时，进队元素大于Q队列尾部的元素，弹出Q尾部的元素下标，重复2；（弹出元素永远不能成为最大值，所以弹出）

3.将该元素放入Q队尾部。（此时可以保证有用元素递减）

Q队头对应的元素即为当前子序列的最大值。

附上一段程序辅助理解（已知量在上面已阐述）。

Q_head = Q_tail = 0; // 队列自己写的，当Q_head < Q_tail时队列非空
for (int i = 1; i <= n; i++) {
    if (Q_head < Q_tail && Q[Q_head] == i - k) Q_head++; // 步骤1
    while (Q_head < Q_tail && A[i] > A[Q[Q_tail]]) Q_tail--; // 步骤2
    Q[Q_tail++] = i; // 步骤3
    B[i] = A[Q[Q_head]]; // 最大值
}

最小值请根据自己的理解自行完成。

这道题又有求最小值，可以采取二分的策略解决此题：确定答案区间、二分折中一个答案、判断答案是否成立、调整区间。

对于判断答案，这题最主要的是要求一个正方形区域的最大值和最小值，如果相减的值>=k，则答案成立。对于求正方形区域的最值，可将平面转化成线性的方式降维处理：将一个ans*ans的正方形拆成ans条线性数组，一趟滑动窗口算法求出每行中所有长度为ans序列的最大/小值，存到一个数组中，再将这个数组纵向处理一趟滑动窗口，此时原本的正方形已经处理成了线性数组，每个ans长的区间的最大/小值即对应了原本的正方形的最值，每次判断答案是否正确。下面将展示伪代码来解释主要内容。

bool check(int size)
    for x = 1 -> n
        Queue1_init(); Queue2_init();
        for i = 1 -> m
            window_put_1(arr[x][i]); // window_put包括了上述3个步骤，后面的_1区分操作队列1（还有队列2），arr指输入数据的矩阵。
            Max[x][i] = arr[Queue1.front()];
            window_put_2(arr[x][i]) // 具体实现和window_put_1不太一样，求的是最大值。这个是求最小值
            Min[x][i] = arr[Queue2.front()];

    for x = size -> m // arr的有效位置是从size开始
        Queue1_init(); Queue2_init();
        for i = 1 -> n
            window_put_1(Max[i][x]); // 注意参数
            window_put_2(Min[i][x]); // 同上
            if (Max[Queue1.front()] - Min[Queue2.front()] >= k) return true; // 判断出答案正确，即存在一个size*size的区间的最大值和最小值之差大于题目中的k

    return false; // 未找到答案，失败

判断矩阵为O(m * n)，二分为O(logn)（保证n<m），总复杂度O(mnlogn)

本题思路讲到这里。剩下的实现靠你们了！