D - New Year's Problem

题意：

n个人。m个商店。

每个商店有对应n个人的n个礼物，每个礼物有一个满意度$a_{i,j}$ ，选择 $n-1$ 个商店使得：所有人能/获得的最大满意度的最小值最大。

Solution：

定义$lie[i]$ 表示第$i$ 个人的最大满意度。

显然，n个人选择n个商店的话，只需要把n个人最大满意度所在的商店选择即可。

根据鸽巢原理，n个人选择n-1的话，必然有两列的最优值在同一行。

我们枚举商店，选择一个商店记录其最大和次大，除去这两个人后，剩下的全部选择最大值即可。

复杂度$O(nm)$

#include <bits/stdc++.h>
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
const int N = 1e5 + 5;
int t, n, m, ans, lie[N], pos1, pos2;
int main()
{
    read(t);
    while(t--)
    {
        read(m); read(n); ans = 0;
        vector<int>v[m+2];
        for(int i = 1; i <= m; i++)
        {
            v[i].push_back(0);
            for(int j = 1, x; j <= n; j++)
            {
                lie[j] = 0;
                read(x);
                v[i].push_back(x);
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                lie[i] = max(lie[i], v[j][i]);
            }
        }
        for(int i = 1; i <= m; i++)
        {
            pos1 = pos2 = 0;
            for(int j = 1; j <= n; j++)
            {
                if(v[i][j] > v[i][pos1]) pos2 = pos1, pos1 = j;
                else if(v[i][j] > v[i][pos2]) pos2 = j;
            }
            int maxnum = min(v[i][pos1], v[i][pos2]);
            for(int j = 1; j <= n; j++)
            {
                if(j == pos1 || j == pos2) continue;
                maxnum = min(maxnum, lie[j]);
            }
            ans = max(ans, maxnum);
        }
        cout << ans << '\n';
    }
    return 0;
}