思路：二分答案 + 二分图匹配

前置知识：

二分答案：如没学过，搞懂https://leetcode.cn/problems/koko-eating-bananas/

二分图匹配：如没学过，搞懂https://leetcode.cn/problems/broken-board-dominoes/

本题原题是：BZOJ 4443: [Scoi2015]小凸玩矩阵

思路：

考虑二分第k大的值。对于二分出来的mid，把矩阵中小于二分出来的答案的，行向列连边跑二分图匹配，看看匹配数是否大于n-k+1。

我们虽然保证了选出来的数一定是第K大的，那我们怎么保证一定有K-1个比这个数大的数能被选出来。由于我们选出来的是最小的第K大，那么如果他不能满足，比他大的肯定也不能满足

JavaScript

// 引入readline模块
const readline = require('readline');

// 创建readline接口实例
const rl = readline.createInterface({
  input: process.stdin, // 设置输入流
  output: process.stdout // 设置输出流
});

let n, m, K, mx; // 定义变量
let myMap = []; // 初始化二维数组

// 逐行读取输入
rl.on('line', (line) => {
  if (!n) { // 如果n未定义
    [n, m, K] = line.split(' ').map(Number); // 读取行数、列数和K值
    mx = 0; // 初始化mx
  } else {
    const row = line.split(' ').map(Number);
    myMap.push([0, ...row]);; // 读取二维数组数据
    mx = Math.max(mx, ...row); // 更新mx
  }
}).on('close', () => { // 读取完毕后执行
  console.log(solve(mx)); // 输出结果
});

// 二分第k大的值的大小
function solve(mx) {
  let l = 1, r = mx;
  let ans = 0;
    
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }

  return ans;
}
// 将小于等于p的元素设为True，大于p的元素设为False，构建匹配图
function check(p) {
  const mp = myMap.map(row => row.map(val => val <= p));
  let ans = 0;
  const match = new Array(m + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    const chw = new Array(m + 1).fill(true);
    if (findMuniu(i, mp, chw, match)) {
      ans++;
    }
  }
  return ans >= n - K + 1;
}
// 这里就是一个匈牙利匹配
function findMuniu(x, mp, chw, match) {
  // 在匹配图中寻找增广路径
  if (!mp[x] || mp[x].length !== m + 1) return false; // 检查mp[x]是否定义且长度正确

  for (let j = 1; j <= m; j++) {
    if (mp[x][j] && chw[j]) {
      chw[j] = false;
      if (match[j] === 0 || findMuniu(match[j], mp, chw, match)) {
        match[j] = x;
        return true;
      }
    }
  }
  return false;
}

Java

import java.util.Scanner;
import java.util.Vector;

public class Main {
    static int n, m, K;
    static Vector<Vector<Integer>> myMap;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        K = scanner.nextInt();
        myMap = new Vector<>(n + 1);

        // 初始化 myMap 并添加 m+1 个子向量
        for (int i = 0; i <= n; i++) {
            myMap.add(new Vector<>(m + 1));
            for (int j = 0; j <= m; j++) {
                myMap.get(i).add(0);
            }
        }

        int mx = 0;

        // 读取用户输入的数字并存储在 myMap 中
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int num = scanner.nextInt();
                myMap.get(i).set(j, num);
                mx = Math.max(mx, myMap.get(i).get(j));
            }
        }

        int result = solve(mx);
        System.out.println(result);
    }

    // 找到一个点的 Muniu 匹配的方法
    static boolean findMuniu(int x, Vector<Vector<Boolean>> mp, Vector<Boolean> chw, Vector<Integer> match) {
        // 遍历 myMap 的列向量中的每个元素
        for (int j = 1; j <= m; j++) {
            // 如果 mp 和 chw 的相应位置为 true 且未匹配
            if (mp.get(x).get(j) && chw.get(j)) {
                // 将 chw 的相应位置设置为 false 并继续匹配
                chw.set(j, false);
                // 如果 match 的相应位置为 0 或者找到了一个新的匹配
                if (match.get(j) == 0 || findMuniu(match.get(j), mp, chw, match)) {
                    // 将 match 的相应位置设置为 x 并返回 true
                    match.set(j, x);
                    return true;
                }
            }
        }
        return false;
    }

    // 检查给定整数 p 是否满足条件
    static boolean check(int p) {
        // 创建一个新的 Vector<Vector<Boolean>> 对象 mp
        Vector<Vector<Boolean>> mp = new Vector<>(n + 1);

        // 为 mp 的每个子向量添加 m+1 个子向量
        for (int i = 0; i <= n; i++) {
            mp.add(new Vector<>(m + 1));
            for (int j = 0; j <= m; j++) {
                mp.get(i).add(false);
            }
        }

        // 遍历 myMap 的行向量中的每个元素
        for (int i = 1; i <= n; i++) {
            // 遍历 myMap 的列向量中的每个元素
            for (int j = 1; j <= m; j++) {
                // 如果 myMap 的行向量中的元素小于等于 p
                mp.get(i).set(j, myMap.get(i).get(j) <= p);
            }
        }

        // 创建一个新的 Vector<Integer> 对象 match
        Vector<Integer> match = new Vector<>(m + 1);
        for (int i = 0; i <= m; i++) {
            match.add(0);
        }

        // 计算满足条件的匹配数
        int ans = 0;
        // 遍历 myMap 的列向量中的每个元素
        for (int i = 1; i <= n; i++) {
            // 创建一个新的 Vector<Boolean> 对象 chw
            Vector<Boolean> chw = new Vector<>(m + 1);
            for (int j = 0; j <= m; j++) {
                chw.add(true);
            }
            // 使用 findMuniu 方法检查是否有一个满足条件的匹配
            if (findMuniu(i, mp, chw, match)) {
                ans++;
            }
        }

        // 如果满足条件的匹配数达到或超过 n-K+1 则返回 true
        return ans >= n - K + 1;
    }

    // 根据给定的最大值 mx 找到满足条件的整数 p 的值
    static int solve(int mx) {
        // 设置变量 l 和 r 的初始值
        int l = 1, r = mx;
        // 设置答案变量 ans 的初始值为 0
        int ans = 0;

        // 使用 while 循环在 l 和 r 之间进行二分查找
        while (l <= r) {
            // 计算中间值 mid
            int mid = (l + r) / 2;
            // 如果满足条件 check(mid) 则更新答案并将 r 设置为 mid-1
            if (check(mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                // 否则将 l 设置为 mid+1
                l = mid + 1;
            }
        }

        // 返回答案
        return ans;
    }
}

Python

def is_match_possible(p, mp, n, m, K):
    # 构建匹配图
    match_graph = [[mp[i][j] <= p for j in range(m + 1)] for i in range(n + 1)]
    matching_count = 0
    matching_result = [0] * (m + 1)

    # 遍历每个元素以寻找增广路径
    for i in range(1, n + 1):
        visited = [True] * (m + 1)
        if find_augmenting_path(i, match_graph, visited, matching_result, m):
            matching_count += 1

    # 检查匹配数是否大于等于 (n - K + 1)
    return matching_count >= n - K + 1

def binary_search(mx, my_map, n, m, K):
    left, right = 1, mx
    result = 0

    while left <= right:
        mid = (left + right) // 2
        if is_match_possible(mid, my_map, n, m, K):
            result = mid
            right = mid - 1
        else:
            left = mid + 1

    return result

def find_augmenting_path(x, match_graph, visited, matching_result, m):
    for j in range(1, m + 1):
        if match_graph[x][j] and visited[j]:
            visited[j] = False
            if matching_result[j] == 0 or find_augmenting_path(matching_result[j], match_graph, visited, matching_result, m):
                matching_result[j] = x
                return True

    return False

def main():
    mx = 0
    n, m, K = map(int, input().split())
    my_map = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        row = list(map(int, input().split()))
        for j in range(1, m + 1):
            my_map[i][j] = row[j - 1]
            mx = max(mx, my_map[i][j])

    print(binary_search(mx, my_map, n, m, K))

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
using namespace std;

int n, m, K; // 声明变量 n, m, K，分别表示行数、列数和第K大元素的数量
vector<vector<int>> myMap; // 声明二维向量 myMap，用于存储输入的数字

// findMuniu 函数：实现匈牙利匹配算法，用于在矩阵中找到一个增广路径
bool findMuniu(int x, vector<vector<bool>>& mp, vector<bool>& chw, vector<int>& match) {
    for (int j = 1; j <= m; j++) {
        if (mp[x][j] && chw[j]) {
            chw[j] = false;
            if (match[j] == 0 || findMuniu(match[j], mp, chw, match)) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

// check 函数：检查给定的数字 p 是否可以添加到匹配图中
bool check(int p) {
    vector<vector<bool>> mp(n + 1, vector<bool>(m + 1, false)); // 声明二维向量 mp，用于存储匹配图

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            mp[i][j] = (myMap[i][j] <= p); // 构建匹配图
        }
    }

    int ans = 0;
    vector<int> match(m + 1, 0); // 声明一维向量 match，用于存储匹配的数字

    for (int i = 1; i <= n; i++) {
        vector<bool> chw(m + 1, true); // 声明一维向量 chw，表示当前可用的数字
        if (findMuniu(i, mp, chw, match)) {
            ans++;
        }
    }

    return ans >= n - K + 1; // 返回匹配数是否大于等于 n - K + 1
}

// solve 函数：使用二分查找算法找到矩阵中可以选出 M!/N! 种组合数组中第 K 大的数字的最小值
int solve(int mx) {
    int l = 1, r = mx;
    int ans = 0;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

// 主函数
int main() {
    cin >> n >> m >> K; // 输入 n, m, K 的值
    myMap.resize(n + 1, vector<int>(m + 1, 0)); // 调整 myMap 的大小

    int mx = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> myMap[i][j]; // 输入矩阵中的数字
            mx = max(mx, myMap[i][j]); // 计算矩阵中的最大值
        }
    }

    int result = solve(mx); // 调用 solve 函数
    cout << result << endl; // 输出结果

    return 0;
}

题目描述

从一个$N*M (N\le M)$的矩阵中选出N个数，任意两个数字不能在同一行或同一列，求选出来的$N$个数中第$K$大的数字的最小值是多少

输入描述

输入矩阵要求:$1 \le K \le N \le M \le 150$

输入格式

N M K

N*M矩阵

输出描述

$N*M$的矩阵中可以选出$\frac{M!}{N!}$种组合数组，每个组合数组中第$K$大的数中的最小值。无需考虑重复数字，直接取字典排序结果即可

样例1

输入

3 4 2
1 5 6 6
8 3 4 3
6 8 6 3

输出

3

说明：N*M的矩阵中可以选出M!/N!种组合数组，每个组合数组中第K大的数中的最小值；上述输入中选出的数组组合为为1,3,6;1,3,3;1,4,8;1,4,3;…

上述输入样例中选出的组合数组有24种，最小数组为1,3,3，则2大的最小值为3

注意：结果是第K大的数字的最小值