Minimax Problem

Created by LXC on Wed Jan 3 20:41:15 2024

https://codeforces.com/problemset/problem/1288/D

ranting: 2000

tag: binary search, bitmasks, dp

problem

给出一个 $n$ 行 $m$ 列的数字矩阵 $a$，找出两行 $x, y$，令 $b_j = \max(a_{x, j}, a_{y, j})$，试使得 $\min\limits_{1 \le j \le m}b_j$ 最大，输出选择的 $x, y$，可以相同。

solution

二分答案，对于当前二分值x，，基于a构造一个新数组c，每个元素视为m位二进制数，对于$a_{i,j}$中大于等于x的将c_{i}的第j位置为1，否则为0。处理完后，c数组存在大量重复，去重后最多只有2^{m}个元素，寻找两个元素使得其与值为m位1则当前x可行。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto& i : a) {
        for (auto& j : i) {
            cin >> j;
        }
    }
    int ans1, ans2;
    ll l = 0, r = 1e9 + 7;
    while (l < r) {
        // cout << l << ' ' << r << endl;
        ll mid = l + r >> 1;
        vector<int> st(1 << m);
        for (int i = 0; i < n; i++) {
            int u = 0;
            for (int j = 0; j < m; j++) {
                u <<= 1;
                if (a[i][j] >= mid)
                    u |= 1;
            }
            st[u] = i + 1;
        }
        int ok = 0;
        for (int i = 0; i < (1 << m); i++) {
            for (int j = 0; j < (1 << m); j++) {
                if (st[i] && st[j] && (i | j) == (1 << m) - 1) {
                    ans1 = st[i], ans2 = st[j];
                    ok = 1;
                }
            }
        }
        if (ok)
            l = mid + 1;
        else
            r = mid;
    }
    cout << ans1 << " " << ans2 << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}