算法

(二分答案)

遇到题目里带有“最大值最小”这种字眼，往往可以用二分答案来尝试。

我们只对每个参数是否超过 mid 感兴趣，所以我们可以根据是否超过 mid 将每个参数压缩为1或0。然后，我们有 $2^5 = 32$ 种参数元组，因此在删除重复项后，我们可以详尽地搜索出可能的 3 个人。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;

int main() {
    int n;
    cin >> n;

    int m = 5;
    vector<vector<int>> a(n, vector<int>(m));
    rep(i, n)rep(j, m) cin >> a[i][j];

    int ac = 0, wa = 1001001001;
    while (ac + 1 < wa) {
        int wj = (ac + wa) / 2;
        vector<int> s;
        rep(i, n) {
            int x = 0;
            rep(j, m) {
                if (a[i][j] >= wj) x |= 1 << j;
            }
            s.push_back(x);
        }
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        bool ok = false;
        rep(i, s.size())rep(j, i + 1)rep(k, j + 1) {
            if ((s[i] | s[j] | s[k]) == (1 << m) - 1) ok = true;
        }
        if (ok) ac = wj; else wa = wj;
    }

    cout << ac << '\n';

    return 0;
}