思路：
先来想想暴力的写法：n 2
枚举左上角的顶点，k 2
求最小值。
考虑优化：
1.答案有单调性，可以二分答案，省去枚举左上角顶点的复杂度。
2.每次c h e c k的时候，将大于该数的设为1，小于该数的设为0，这样就可以在k 2
枚举的时候用二维前缀和O ( 1 )查询了。
注意下边界问题，用第几小或第几大都是能过的。
代码：
第几小
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const int maxn=3e5+100; const double eps=1e-7; ll n,k,a[810][810],s[810][810],idx; bool check(ll x){ memset(s,0,sizeof s); rep(i,1,n) rep(j,1,n) if(a[i][j]<=x) s[i][j]=1; else s[i][j]=0; rep(i,1,n) rep(j,1,n) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j]; for(int i=1;i+k-1<=n;i++){ for(int j=1;j+k-1<=n;j++){ ll x2=i+k-1,y2=j+k-1; ll x1=i,y1=j; ll sum=s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1]; if(sum>=idx) return 1; } } return 0; } int main(){ n=read,k=read; idx=(k*k); if(idx%2) idx=idx/2+1; else idx=idx/2; ll l=1e9+1,r=-1,res; rep(i,1,n) rep(j,1,n){ a[i][j]=read; l=min(l,a[i][j]); r=max(r,a[i][j]); } while(l<=r){ ll mid=(l+r)/2; if(check(mid)) r=mid-1,res=mid; else l=mid+1; //cout<<l<<"*****"<<r<<"*****"<<mid<<"\n"; } printf("%lld\n",res); return 0; }
第几大
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const int maxn=3e5+100; const double eps=1e-7; ll n,k,a[810][810],s[810][810],idx; bool check(ll x){ memset(s,0,sizeof s); rep(i,1,n) rep(j,1,n) if(a[i][j]>x) s[i][j]=1; else s[i][j]=0; rep(i,1,n) rep(j,1,n) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j]; for(int i=1;i+k-1<=n;i++){ for(int j=1;j+k-1<=n;j++){ ll x2=i+k-1,y2=j+k-1; ll x1=i,y1=j; ll sum=s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1]; if(sum<idx) return 1; } } return 0; } int main(){ n=read,k=read; idx=(k*k)/2+1; ll l=1e9+1,r=-1,res; rep(i,1,n) rep(j,1,n){ a[i][j]=read; l=min(l,a[i][j]); r=max(r,a[i][j]); } while(l<=r){ ll mid=(l+r)/2; if(check(mid)) r=mid-1,res=mid; else l=mid+1; //cout<<l<<"*****"<<r<<"*****"<<mid<<"\n"; } printf("%lld\n",res); return 0; }
