样例输入
【样例1】
3 2 1 7 0 5 8 11 10 4 2
【样例2】
3 3 1 2 3 4 5 6 7 8 9
样例输出
【样例1】
4
【样例2】
5
据说这个题用对顶堆维护被卡了
先挂一手官方该题题解链接
大体思路：
二分，将原 矩阵 根据二分的值变成01矩阵,如果元素值> val 就变为1,否则0
对于k * k 的矩阵,统计区域内元素之和，如果 sum < ⌊k2 / 2⌋ + 1,意味着当前k * k矩阵的中位数小于x，而x是我们的答案(最小中位数)，
①sum < ⌊k2 / 2⌋ + 1 情况下x取得太大，r = mid
②反之，x还可能取更小的，l = mid
但是需要注意下l的初始值，当取0 or 1的时候是会wa掉的：
下限要取-1
typedef int itn; int a[809][809]; int s[809][809]; int main() { int n = read,k = read; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { a[i][j] = read; } } int p = k * k / 2 + 1; int l = -1,r = 0x3f3f3f3f; bool flag = 0; while(l + 1 < r) { int mid = l+r >> 1; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j]; if(a[i][j] > mid) s[i+1][j+1] ++; } } flag = 0; for(int i=0; i<n-k+1; i++) { for(int j=0; j<n-k+1; j++) { int val = s[i+k][j+k] + s[i][j] - s[i][j+k] - s[i+k][j]; if(val < p) { flag = 1; break; } } if(flag) break; } if(flag) r = mid; else l = mid; } cout << l + 1 <<endl; return 0; }
