欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforces 1288 D 二分+二进制check

程序员文章站 2022-04-04 20:04:49
...

题目链接:https://codeforces.com/contest/1288/problem/D
题目大意:codeforces 1288 D 二分+二进制check
二分一个最小值。考虑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;
}
相关标签: 二进制