求条
查看原帖
求条
1169788
xiaokang_suancai楼主2025/7/3 11:22

题目如下:

T625457 中位数

题目描述

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

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

S={Ap,qipi+m1,  jqj+m1}.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 中元素按非升序排列为

s1s2sm2s_1 \ge s_2 \ge \cdots \ge s_{m^2}

则该子矩阵的中位数定义为 sks_k

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

输入格式

输入格式

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

接下来的 nn 行,每行包含 nn 个整数,第 ii 行第 jj 列的整数即为 Ai,jA_{i,j}

输出格式

输出一个整数 xx,表示所选 m×mm\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×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\% 的数据,1mn31 \le m \le n \le 3

对于 100%100\% 的数据,1mn8001 \le m \le n \le 8000Ai,j1090 \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;
}

程序一直输出 11,求条 qwp

2025/7/3 11:22
加载中...