题目如下:
给定一个大小为 n×n 的矩阵 A=(Ai,j)1≤i,j≤n,你需要从中选择一个大小为 m×m 的子矩阵(即选定行区间 [i,i+m−1] 与列区间 [j,j+m−1],1≤i,j≤n−m+1),使得该子矩阵内所有 m2 个元素的“中位数”最小。
定义:令子矩阵内所有元素构成多重集
S={Ap,q∣i≤p≤i+m−1,j≤q≤j+m−1}.记 k=⌊2m2⌋+1。将 S 中元素按非升序排列为
s1≥s2≥⋯≥sm2则该子矩阵的中位数定义为 sk。
求所有可能的 m×m 子矩阵的中位数中的最小值。
第一行包含两个整数 n 和 m,分别表示矩阵的行/列数和要选取的子矩阵的尺寸,满足 1≤m≤n。
接下来的 n 行,每行包含 n 个整数,第 i 行第 j 列的整数即为 Ai,j。
输出一个整数 x,表示所选 m×m 子矩阵中位数的最小可能值。
3 2
1 7 0
5 8 11
10 4 2
4
3 3
1 2 3
4 5 6
7 8 9
5
所有 2×2 子矩阵及其中位数如下:
因此最小中位数为 4。
仅有一个 3×3 子矩阵,全体元素排序后为 {1,2,3,4,5,6,7,8,9},中位数为第 ⌊9/2⌋+1=5 大的数 5。
对于 40% 的数据,1≤m≤n≤3。
对于 100% 的数据,1≤m≤n≤800,0≤Ai,j≤109。
我的代码(蒟蒻代码,轻喷 ):
#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