算法
(二分答案、二维前缀和) $O(n^2\log \max\{A_i\})$
题意:在 $N \times N$ 的矩阵中挖一个 $K \times K$ 的子矩阵出来,问它们的中位数最小是多少。
这里的中位数指的是第 $\lfloor \frac{K^2}{2}\rfloor + 1$ 大的数
暴力的时间复杂度为 $O(n^2k^2\log k^2)$,显然过不去。
令 $L = \lfloor \frac{K^2}{2}\rfloor + 1$
注意到本题满足“答案是否不超过 $X$ ?”这点,所以可以进行二分。
对于这个数据来说,
3 2
1 7 0
5 8 11
10 4 2
若 $x = 4$,则原矩阵将变成
0 1 0
1 1 1
1 0 0
中位数为 $0 \ \Rightarrow$ 第 $L$ 大的数为 $0\ \Rightarrow 1$ 不足 $L$ 个 $\Rightarrow$ 该子矩阵的和不足 $L$
如果对于某个 $K \times K$ 的子矩阵的和不足 $L$ 则为 Yes
,反之为 No
类题:
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
int main() {
int n, k;
cin >> n >> k;
vector a(n, vector<int>(n));
rep(i, n)rep(j, n) cin >> a[i][j];
int L = k * k / 2 + 1;
int wa = -1, ac = 1001001001;
while (wa + 1 < ac) {
int wj = (wa + ac) / 2;
bool ok = false;
{
vector s(n + 1, vector<int>(n + 1));
rep(i, n)rep(j, n) s[i + 1][j + 1] = a[i][j] > wj;
rep(i, n + 1)rep(j, n) s[i][j + 1] += s[i][j];
rep(i, n)rep(j, n + 1) s[i + 1][j] += s[i][j];
rep(i, n - k + 1)rep(j, n - k + 1) {
int now = s[i + k][j + k];
now -= s[i][j + k];
now -= s[i + k][j];
now += s[i][j];
if (now < L) ok = true;
}
}
if (ok) ac = wj; else wa = wj;
}
cout << ac << '\n';
return 0;
}