Link: D. Minimax Problem

D. Minimax Problem

Description:

Example
input
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
output
1 5

Problem solving:
这道题的意思就是给你n个长度为m的序列，你可以任选两个序列经过操作变成一个序列。操作规则：新序列的第i位的值为你选择的两个序列中对应位置的两个数中的最大值。现在让你选两个序列使他们组成的新序列中的最小值最大。

遇到最小的最大，很容易就应该想到是二分，但是这道题看起来似乎不是那么容易二分。难点也就是check函数。看了dl视频之后才知道原来还可以这样二分

我们假设现在是在进行check(x)，首先我们把这n个序列中每个大于x的值标为1，把小于x的值标为0。全部改完之后可以看成是一个m位的二进制。然后还可以发现只要存在两个序列转换之后的“二进制”相互或一下可以变成m位都是1的话，这个x就是可行的。（虽然没有严谨的证明，但是可以自己想一下，确实是这样的）
至于m位全是1的判断，我们可以直接看这个数与(i<<m)-1是否相等即可

这样我们check就可以写好了，然后二分答案即可。因为m最多是8位，也就是256，平方一下还不到1e6.所以时间复杂度可以过的去。
Code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int       r, l, n, m, a[maxn][10], mid, ans, ans1, ans2, val[(1 << 8) + 10], flag;
bool check(int x)
{
    flag = 0; memset(val, 0, sizeof(val));
    for (int i = 0; i < n; i++)
    {
        int mi = 0;
        for (int j = 0; j < m; j++)
            if (a[i][j] >= x)
                mi += (1 << j);//(1<<j)即第j位为1时的值，累加起来就是这m位二进制表示的值
        val[mi] = i + 1;//值位mi的是第i列，因为从0开始的所以加1
    }
    /*看能否找到满足最大的最小值为x的两列*/
    for (int i = 0; i < (1 << m); i++)
        for (int j = 0; j < (1 << m); j++)
            if (val[i] != 0 && val[j] != 0 && ((i | j) == (1 << m) - 1))//如果i和j的val不是0说明出现过
                flag = 1, ans1 = val[i], ans2 = val[j];
    return flag;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    l = -1, r = 1e9;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    check(ans);
    cout << ans1 << " " << ans2 << endl;
    return 0;
}
赏