CodeForces 1288D :Minimax Problem 二分

本文主要是介绍CodeForces 1288D :Minimax Problem 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题目描述

给出一个 $n$ 行 $m$ 列的数字矩阵 $a$ ,找出两行 $x, y$ ,令 $b_j=max(a_{x,j},a_{y,j})$ ,试使得 $\min\limits_{1\le j \le m}b_j$ 最大，输出选择的 $x, y$ ,可以相同

分析

比较有意思的题目
首先，求最小值的最大，大概就是朝二分那个方向想了，关键怎么去写这个check函数
我们去二分这个答案，如果a[i][j] >= ans，我们赋值为1，否则赋值为0，因为两个序列相同的位置必须至少每一位有一个数大于等于ans，所以我们去枚举一个序列，然后dfs每一个位置0和1的状态，如果这一位为1，那么另一个序列是1或者0都可以，如果为0，那么另一个序列这一位必定为1

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 10;
const ll mod= 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
int gcd(int a,int b){return (b>0)?gcd(b,a%b):a;}
int a[N][10];
int b[N];
int ans1,ans2;
int id;
map<int,int> M;
int n,m;int find(int res,int x){if(x == -1){if(M[res]) {ans2 = M[res];return true;}return false;}if(b[id] & (1 << x)){if(find(res | (1 << x),x - 1)) return true;return find(res,x - 1);}else{return find(res + (1 << x),x - 1);}
}bool check(int mid){M.clear();for(int i = 1;i <= n;i++){int res = 0;for(int j = 0;j < m;j++) res += ((a[i][j] >= mid) << j);if(res == (1 << m) - 1) {ans1 = i,ans2 = i;return true;}b[i] = res;M[res] = i;}for(int i = 1;i <= n;i++){id = i;if(find(0,m - 1)){ans1 = i;return true;}}return false;
}int main(){read(n),read(m);for(int i = 1;i <= n;i++)for(int j = 0;j < m;j++) read(a[i][j]);int l = 0,r = INF;while(l < r){int mid = (l + r + 1)>> 1;if(check(mid)) l = mid;else r = mid - 1;}if(ans1 + ans2 == 0) ans1 = 1,ans2 = 1;printf("%d %d\n",ans1,ans2);return 0;
}/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/