题目链接:https://codeforces.com/contest/1288/problem/D
题目大意:
二分一个最小值。考虑check。
我们去原数组,如果a[i][j]>=mid。为1,否则为0。那么把每一行压缩成一个二进制数。放入桶中。再去桶里枚举i, j。如果i|j=(1<<m)-1说明满足这个最小值。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int a[300005][10];
int b[300005];
int n, m, x, y;
int check(int mid){
int c[1024]={0};
for(int i=1; i<=n; i++){
int t=0;
for(int j=1; j<=m; j++){
if(a[i][j]>=mid){
t+=(1<<(j-1));
}
}
c[t]=i;
}
for(int i=0; i<(1<<m); i++){
for(int j=0; j<(1<<m); j++){
if(c[i]&&c[j]&&(i|j)==(1<<m)-1){
x=c[i], y=c[j];
return 1;
}
}
}
return 0;
}
int main(){
int ansx, ansy;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
scanf("%d", &a[i][j]);
}
}
int L=0, R=1e9;
while(L<=R){
int mid=(L+R)/2;
if(check(mid)){
L=mid+1;
ansx=x, ansy=y;
}
else{
R=mid-1;
}
}
printf("%d %d\n", ansx, ansy);
return 0;
}