1619D. New Year‘s Problem

题目链接

首先我们遍历所有行，得到每一列的最大值，由此我们得到了在选择 k （ k ≤ n k（kleq n k（k≤n）家商店的情况下最大 α alpha α的取值 （因为总共就送给 n n n个人礼物，所以选择的商店数量不会大于 n n n）。分以下两种情况：

• 每一家商店买一个礼物。这时选取的商家数超过了我们限定选取的 n − 1 n - 1 n−1家，所以我们可以采取两家合并为一家的策略，去掉两家商店然后选择一家商店的两个礼物，为了最优的条件，我们肯定会选取这一行最大的两个值，由于 α = m i n { a 1 , a 2 , . . . , a n } alpha=min{a_1,a_2,...,a_n} α=min{a1​,a2​,...,an​}，所以 α alpha α的取值也只和这一行的次大值有关了，为了使次大值最大，我们会选择 c c c，所以为了最优必定会选择了 c c c所处的那一行，然后比较 c c c和 a [ 0 ] a[0] a[0]的值，较小值即为 α alpha α的值。
• 其中一家商店买两个及以上的礼物。此时一家商店会选到这一家店第二大或第三大的礼物，由于 c c c是每一行第二大的最大值，所以这时的 a [ 0 ] a[0] a[0]必定小于 c c c， m i n ( c , a [ 0 ] ) min(c,a[0]) min(c,a[0])必定会输出 c c c。

#include
#include
using namespace std;
const int N = 1e5+5;
int a[N], b[N];
int main(){
    int t;cin>>t;
    while(t --){
        int n, m, c = 0;cin>>n>>m;
        for(int i = 0; i < m; i ++) a[i] = 0;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j ++){
                cin>>b[j]; a[j]=max(a[j],b[j]);
            }
            sort(b, b + m);
            c = max(c, b[m - 2]);
        }
        sort(a, a + m);
        cout<