题意:有\(n\)x\(n\)的矩阵,用\(k\)x\(k\)的小矩阵去遍历整个矩阵,求所有\(k\)x\(k\)矩阵中遍历时的最小中位数.

题解:二分答案.将原矩阵根据二分的值变成01矩阵,如果元素值不小于\(x\)就变为\(1\),否则就是\(0\).对于某个\(k\)x\(k\)的小矩阵,统计它的元素和,如果它的和\(sum<\lfloor \frac{k^2}{2}\rfloor+1\),意味着当前小矩阵的中位数小于\(x\),而\(x\)是我们要的答案,即最小中位数,所以当前不合法,\(x\)取大了,此时就要缩小右区间,如果全部都跑完了之后没有出现不合法的情况,就说明\(x\)可能取小了,那么更新左区间.矩阵和可以用矩阵前缀和维护出来.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n,k;
ll a[900][900];
ll s[900][900];

bool check(int x){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]>=x);
		}
	}

	for(int i=k;i<=n;++i){
		for(int j=k;j<=n;++j){
			if(s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k]<(k*k/2)+1){
				return false; //x大了
			}
		}
	}
	return true; //x小了
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>k;

	rep(i,1,n){
		rep(j,1,n){
			cin>>a[i][j];
		}
	}
	int l=0,r=1e9+10;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}


	cout<<l<<'\n';

    return 0;
}