社区讨论

求条

xxiaokang_suancai
题目总版参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mcmtmrni
此快照首次捕获于
2025/07/03 11:23
8 个月前
此快照最后确认于
2025/07/03 11:25
8 个月前
查看原帖
题目如下：

T625457 中位数

题目描述

给定一个大小为 n×nn\times n 的矩阵 A=(Ai,j)1≤i,j≤nA = \bigl(A_{i,j}\bigr)_{1 \le i,j \le n}，你需要从中选择一个大小为 m×mm\times m 的子矩阵（即选定行区间 [i,i+m−1][i,i+m-1] 与列区间 [j,j+m−1][j,j+m-1]，1≤i,j≤n−m+11 \le i,j \le n-m+1），使得该子矩阵内所有 m2m^2 个元素的“中位数”最小。
定义：令子矩阵内所有元素构成多重集
S={ Ap,q∣i≤p≤i+m−1,  j≤q≤j+m−1}.S = \{\,A_{p,q}\mid i \le p \le i+m-1,\;j \le q \le j+m-1\}.
记 k=⌊m22⌋+1k = \bigl\lfloor \tfrac{m^2}{2}\bigr\rfloor + 1。将 SS 中元素按非升序排列为
s1≥s2≥⋯≥sm2s_1 \ge s_2 \ge \cdots \ge s_{m^2}
则该子矩阵的中位数定义为 sks_k。
求所有可能的 m×mm\times m 子矩阵的中位数中的最小值。

输入格式

输入格式

第一行包含两个整数 nn 和 mm，分别表示矩阵的行/列数和要选取的子矩阵的尺寸，满足 1≤m≤n1 \le m \le n。
接下来的 nn 行，每行包含 nn 个整数，第 ii 行第 jj 列的整数即为 Ai,jA_{i,j}。

输出格式

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

输入输出样例 #1

输入 #1

CPP
3 2
1 7 0
5 8 11
10 4 2

输出 #1

CPP
4

输入输出样例 #2

输入 #2

CPP
3 3
1 2 3
4 5 6
7 8 9

输出 #2

CPP
5

说明/提示

样例 1 解释

所有 2×22\times2 子矩阵及其中位数如下：
  1. 行列区间 [1,2]×[1,2][1,2]\times[1,2]：{1,7,5,8}\{1,7,5,8\}，中位数为第 ⌊4/2⌋+1=3\lfloor 4/2\rfloor+1=3 大的数，即 55
  2. 区间 [1,2]×[2,3][1,2]\times[2,3]：{7,0,8,11}\{7,0,8,11\}，中位数 =7=7
  3. 区间 [2,3]×[1,2][2,3]\times[1,2]：{5,8,10,4}\{5,8,10,4\}，中位数 =5=5
  4. 区间 [2,3]×[2,3][2,3]\times[2,3]：{8,11,4,2}\{8,11,4,2\}，排序后为 {2,4,8,11}\{2,4,8,11\}，中位数 =4=4
因此最小中位数为 44。

样例 2 解释

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

数据范围

对于 40%40\% 的数据，1≤m≤n≤31 \le m \le n \le 3。
对于 100%100\% 的数据，1≤m≤n≤8001 \le m \le n \le 800，0≤Ai,j≤1090 \le A_{i,j} \le 10^9。
我的代码（蒟蒻代码，轻喷 ）：
CPP
#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;
}
程序一直输出 11，求条 qwp

回复

共 0 条回复，欢迎继续交流。

正在加载回复...