T3 AcWing 4863. 构造新矩阵

二分 + 抽屉原理

整理体面要求

思路

二分

首先我们找到每一列最大值的集合 的最小值 且选取的列数不能超过行数, 即不是一个方矩阵

最大值的最小值,我们首先想到用二分去做.

在一个数轴上分为两个区间, 成立和不成立的区间,

如果mid小于我们要求的答案, 那么永远成立,否则不成立

抽屉原理

在check函数中,我们要验证给定的mid是否符合要求

如果行列都等于n

那么我们只需要求一行中至少有一个数大于mid即可,

但是题目要求的是列数小于行数- 1

所以有某一列,一定有两个数成立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
int n,m;
bool check(int x,vector<vector<int>> &ma)
{
  	// 定义每一行是否有大于x的数
    vector<int> st(m,0);
    bool same = false;
    for(int i = 0; i < n; i++)
    {
      	// 扫描每一列
        bool flag = false;
        for(int j = 0; j < m; j++)
        {
            if(ma[j][i] >= x)
            {   
                flag = true;
              	// 如果某一行已经有一个大于x的数,则有一行有两个以上大于x
                if(st[j] == 1) same = true;
                else st[j] = 1;
            }
        }
      	// 某一行没有大于x的数字, 直接返回false;
        if(!flag) return false;
    }
  
  	// 一行有两个大于x 的数,才能成立
    return same;
}


int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> m >> n;
        vector<vector<int>> ma(m,vector(n,0));
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                cin >> ma[i][j];
        
      	// 二分求答案
        int l = 1, r = 0x3f3f3f3f;
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(check(mid,ma)) l = mid;
            else r = mid - 1;
        }
        
        cout << l << endl;
    }
    
    return 0;
}