CodeForces1288D - Minimax Problem（二分 + 状压）

传送门：CodeForces - 1288D

题目描述

You are given n arrays $a_1, a_2, …, a_n$; each array consists of exactly m integers. We denote the y-th element of the x-th array as $a_{x,y}$.

You have to choose two arrays $a_i and a_j $(1≤i,j≤n, it is possible that i=j). After that, you will obtain a new array b consisting of m integers, such that for every $k$ $\in [1,m] b_k=max(a_{i,k},a_{j,k}$)

Your goal is to choose i and j so that the value of $min(b_1,b_2,…,b_m)$ is maximum possible.

输入描述

The first line contains two integers n and m $(1≤n≤3⋅10^5, 1≤m≤8)$ — the number of arrays and the number of elements in each array, respectively.

Then n lines follow, the x-th line contains the array ax represented by $m$ integers $a_{x,1}, a_{x,2}, …, a_{x,m} (0≤a_{x,y}≤10^9).$

输出描述

Print two integers i and j (1≤i,j≤n, it is possible that i=j) — the indices of the two arrays you have to choose so that the value of $min(b_1,b_2,…,b_m)$ is maximum possible. If there are multiple answers, print any of them.

思路分析

有n个长度为m的数组，每次选择两个数组，可以是相同的，然后对于每一个下标取最大值，得到一个新数组，求新数组的最小值的最大值。
最小值最大问题，首先考虑二分答案，由于长度最多只有8，可以进行状态压缩。
对于check，每次的mid，对每个数组的每一位进行判断，如果>=mid，则该位为1，最后得到一个二进制数，将每个二进制状态的数组标记，最后只需要暴力枚举两个状态 $i|j==(1<<m)-1$就可以

样例输入

6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0

样例输出

1 5

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int INF = 0x3f3f3f3f;
const int N=3e5+10;

int a[N][9],vis[1<<8];
int n,m,ax,ay;

int check(int mid){
    mem(vis,0);
    for(int i=1;i<=n;i++){
        int s=0;
        for(int j=1;j<=m;j++){
            if(a[i][j]>=mid){
                s+=(1<<(j-1));
            }
        }
        vis[s]=i;
    }
    for(int i=0;i<(1<<m);i++){
        for(int j=0;j<(1<<m);j++){
            if(vis[i]&&vis[j]&&(i|j)==(1<<m)-1){
                ax=vis[i];
                ay=vis[j];
                return 1;
            }
        }
    }
    return 0;
}


int main() {
    IOS;
    int ma=-INF;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            ma=max(ma,a[i][j]);
        }
    }
    int l=0,r=ma;
    while(r>=l){
        int mid=(l+r)/2;
        if(check(mid)){
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<ax<<" "<<ay<<endl;
    return 0;
}