题意：给你一个n * m 的矩阵。让你在这个矩阵里面找一个一个矩阵，使得这个矩阵的四个角的值最小值最大。
思路：最小值最大，可以考虑二分。那怎么二分呢？我们可以二分枚举答案，即四个角的最小值，然后带入验证即可。怎么验证呢？
枚举出最小值后，带入，把每一行大于等于最小值的值先存起来，然后枚举配对。并且标记，如果枚举配对的列已经枚举过了，那么直接返回1,这说明还可能比这个最小值还大的值，先存起来这个最小值，然后继续二分枚举。
AC Code：
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<stack> #include<cmath> #include<cstdio> #include<iomanip> #include<sstream> #include<algorithm> using namespace std; #define read(x) scanf("%d",&x) #define Read(x,y) scanf("%d%d",&x,&y) #define sRead(x,y,z) scanf("%d%d%d",&x,&y,&z) #define gc(x) scanf(" %c",&x); #define mmt(x,y) memset(x,y,sizeof x) #define write(x) printf("%d\n",x) #define INF 0x3f3f3f3f #define ll long long #define mod 998244353 #define pdd pair<double,double> const int N = 50010; const int M= 1e6+5; int res[1010][1010]; bool vis[1010][1010]; int f[1010]; int n,m; bool ok(int x){//验证 mmt(vis,0); for(int i = 1;i <= n;++i){ int tot = 0; for(int j = 1;j <= m;++j){ if(res[i][j] >= x) f[++tot] = j; } for(int j = 1;j <= tot - 1;++j){ for(int k = j+1;k <= tot;++k){ if(vis[f[j]][f[k]]) return 1; vis[f[j]][f[k]] = 1; } } } return 0; } int main() { Read(n,m); int MAX = -INF; for(int i = 1;i <= n;++i){ for(int j = 1;j <= m;++j){ read(res[i][j]); MAX = max(MAX,res[i][j]); } } int l = 0, r = MAX; while(l < r){//二分枚举 int mid = l + r + 1>> 1; if(ok(mid)) l = mid ; else r = mid - 1; } cout<<l<<endl; }
