题目如下：

T625457 中位数

题目描述

给定一个大小为 $n\times n$ 的矩阵 $A = \bigl(A_{i,j}\bigr)_{1 \le i,j \le n}$，你需要从中选择一个大小为 $m\times m$ 的子矩阵（即选定行区间 $[i,i+m-1]$ 与列区间 $[j,j+m-1]$，$1 \le i,j \le n-m+1$），使得该子矩阵内所有 $m^2$ 个元素的“中位数”最小。

定义：令子矩阵内所有元素构成多重集

$$S = \{\,A_{p,q}\mid i \le p \le i+m-1,\;j \le q \le j+m-1\}.$$

记 $k = \bigl\lfloor \tfrac{m^2}{2}\bigr\rfloor + 1$。将 $S$ 中元素按非升序排列为

$$s_1 \ge s_2 \ge \cdots \ge s_{m^2}$$

则该子矩阵的中位数定义为 $s_k$。

求所有可能的 $m\times m$ 子矩阵的中位数中的最小值。

输入格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示矩阵的行/列数和要选取的子矩阵的尺寸，满足 $1 \le m \le n$。

接下来的 $n$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 列的整数即为 $A_{i,j}$。

输出格式

输出一个整数 $x$，表示所选 $m\times m$ 子矩阵中位数的最小可能值。

输入输出样例 #1

输入 #1

3 2
1 7 0
5 8 11
10 4 2

输出 #1

4

输入输出样例 #2

输入 #2

3 3
1 2 3
4 5 6
7 8 9

输出 #2

5

说明/提示

样例 1 解释

所有 $2\times2$ 子矩阵及其中位数如下：

1. 行列区间 $[1,2]\times[1,2]$：$\{1,7,5,8\}$，中位数为第 $\lfloor 4/2\rfloor+1=3$ 大的数，即 $5$
2. 区间 $[1,2]\times[2,3]$：$\{7,0,8,11\}$，中位数 $=7$
3. 区间 $[2,3]\times[1,2]$：$\{5,8,10,4\}$，中位数 $=5$
4. 区间 $[2,3]\times[2,3]$：$\{8,11,4,2\}$，排序后为 $\{2,4,8,11\}$，中位数 $=4$

因此最小中位数为 $4$。

样例 2 解释

仅有一个 $3\times3$ 子矩阵，全体元素排序后为 $\{1,2,3,4,5,6,7,8,9\}$，中位数为第 $\lfloor9/2\rfloor+1=5$ 大的数 $5$。

数据范围

对于 $40\%$ 的数据，$1 \le m \le n \le 3$。

对于 $100\%$ 的数据，$1 \le m \le n \le 800$，$0 \le A_{i,j} \le 10^9$。

---

我的代码（蒟蒻代码，轻喷 ）：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[805][805],l,r,mid,ans,k,maxn=-1;
bool b[805][805];
int s[805][805];
// b 数组用来存元素是否大于 x 
// s 数组是 b 的二维前缀和数组 
bool check(int x)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]>x)
				b[i][j]=1; // 生成 b 数组 
			else
				b[i][j]=0;
			//cout<<b[i][j]<<' ';
		} 
		//cout<<endl;
	}
	//cout<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			s[i][j]=b[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			// 生成 s 数组 
			//cout<<s[i][j]<<' ';
		}
		//cout<<endl;
	}
	//cout<<endl;
	for(int i=1;i<=n-m+1;i++)
	{
		for(int j=1;j<=n-m+1;j++)
		{
			int sum=s[i+m-1][j+m-1]-s[i][j+m-1]-s[i+m-1][j]+s[i][j];
			//cout<<sum<<' ';
			if(sum<k)
				return true;
			// 如果子矩阵中大于 x 的元素数量小于 k，说明这个子矩阵的中位数一定小于等于 x 
		}
		//cout<<endl;
	}
	//cout<<endl;
	return false;
}
int main()
{
	cin>>n>>m;
	k=m*m/2+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			maxn=max(maxn,a[i][j]);
		}
	l=1,r=maxn;
	while(l<r) // 二分答案 
	{
		mid=(l+r)>>1;
		memset(b,0,sizeof(b));
		memset(s,0,sizeof(s));
		if(check(mid))
		{
			r=mid;
			ans=mid;
		}
		else
			l=mid+1;
	}
	cout<<ans;
	return 0;
}

程序一直输出 $1$，求条 qwp