You are given 𝑛 arrays 𝑎1, 𝑎2, ..., 𝑎𝑛; each array consists of exactly 𝑚 integers. We denote the 𝑦-th element of the 𝑥-th array as 𝑎𝑥,𝑦.

You have to choose two arrays 𝑎𝑖 and 𝑎𝑗 (1≤𝑖,𝑗≤𝑛, it is possible that 𝑖=𝑗). After that, you will obtain a new array 𝑏 consisting of 𝑚 integers, such that for every k[1,m]k \in [1, m] bk=max(ai,k,aj,k)b_k = \max(a_{i, k}, a_{j, k}) .

Your goal is to choose 𝑖𝑖 and 𝑗𝑗 so that the value of minmink=1mbk\min \limits_{k = 1}^{m} b_k is maximum possible.

大致题意 📖

给你n(<=3e5)n ( <= 3e5) 个数组,每个数组有m(<=8)m (<= 8) 个数
选择两个数组 ai,aja_i,a_j , ii 可以等于jj
定义数组bb的每个项 k[1,m]k \in [1, m] bk=max(ai,k,aj,k)b_k = \max(a_{i, k}, a_{j, k}) .
定义s=mink=1mbks = \min \limits_{k = 1}^{m} b_k
i,ji,j,使ss最大

链接 🔗

「CodeForces 1288D」 Minimax Problem

题解 ❓

直接求显然很麻烦,注意到(m <= 8)我们考虑二分
单调性很显然,可以感性理解
接着考虑如何判断xx是否满足条件
直接枚举是n2n^2的,但是因为我们只需要验证是否能每项都大于xx,所以我们可以将每个大于等于xx的数变成1,小于xx的数变成0
这样的所有数组都会变成最多长为8位的0,10,1数组,最多有282^8个不同的数组
因此我们可以直接枚举这个数组 O(256256)O(256 * 256),即考虑是否存在两个数组的 全为11

代码

const int maxd = 3e5+10;
ll a[maxd][10],ansl,ansr,n,m,vis[300];
bool check(ll x)
{
    memset(vis,0,sizeof(vis));
    FOR(i,1,n)
    {
        ll now = 0;
        FOR(j,1,m) if(a[i][j] >= x) now |= 1<<(j-1);
        vis[now] = i;
    }
    F(1<<m)
        FOR(j,0,(1<<m)-1)
        if(vis[i] && vis[j] && ( (i|j) == (((1<<m)-1))))
        {
            ansl = vis[i], ansr = vis[j];
            return true;
        }
    return false;
}
int main()
{
//    __IN;__OUT;
    RLL2(n ,m);
    FOR(i,1,n) FOR(j,1,m) RLL(a[i][j]);
    ll l = 0,r = 1e9;
    while(l<=r)
    {
        ll x = (l+r)>>1;
        if(check(x)) l = x+1;
        else r = x-1;
    }
    PLN2(ansl,ansr);
    return 0;
}