codeforces 1288 D 二分+二进制check

标签: 二进制

题目链接: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;
}
版权声明:本文为qq_21433411原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_21433411/article/details/103990820