题面描述

小塔的集训队共有 $n$ 个人，每个人都有 $m$ 个属性。现在需要从中挑选出 $k$ 个人组成战队。战队的属性计算方式是所选 $k$ 个人对应属性的最大值。战队的战斗力取决于这些属性最大值中的最小值，即 $m$ 个属性的最大值的最小值。目标是选择队员使战队的战斗力最大化，请输出战队的最高战斗力。

思路

求最大值容易想到二分答案，将大于$mid$的看作$1$，其他看作$0$,如果不超过$k$个数或起来为(1<<m)-1,那么说明当前的$mid$满足条件

思路讲解

1.二分搜索：

初始化 left = 1 和 right = 1000。 通过二分搜索缩小范围，找到最大的满足条件的 mid 值。

2.掩码表示：

对于每个候选人，我们计算一个掩码 mask，其中每个比特位表示某个属性是否大于等于 mid。 例如，若某个候选人的属性值为 [4, 4, 1, 1]，对于 mid = 4，则掩码为 0b0011（表示第1和第2个属性大于等于4）。

3.位掩码动态规划：

我们定义 dp[mask]，表示覆盖 mask 所需的最少人数。 初始状态下，dp[0] = 0，即不需要任何人即可覆盖空属性。 通过枚举所有掩码组合，计算能够覆盖的最大属性集合并更新最少人数。

4.判断可行性：

如果可以用不超过 k 个人覆盖所有属性，即 dp[(1 << m) - 1] <= k，则当前 mid 可行。

5.更新结果：

如果 mid 可行，记录结果并尝试更大的 mid。 否则，尝试更小的 mid。

时间复杂度分析

时间复杂度分析

1.二分搜索复杂度：由于战斗力范围为1到1000，因此二分搜索的时间复杂度为 $O(\log(1000)) = O(10)$。

2.掩码处理复杂度：每次二分查找时，需要遍历所有候选人的属性，计算掩码，并通过位掩码动态规划更新 dp 数组，时间复杂度为 $O(n \times m +2^{2m})$。

3.总体复杂度：总体时间复杂度为 $O(T \cdot n \cdot m \ \cdot \log(1000))$，其中 $T$ 是测试数据组数，n 是候选人数，m 是属性个数。由于 $m \leq 10$，时间复杂度是可以接受的

cpp

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9; // 定义一个足够大的常数，用于初始化DP数组

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int T; // 测试数据组数
	cin >> T;
	
	while(T--){
		int n, m, k;
		cin >> n >> m >> k; // 读取候选人数量n，属性数量m，选择人数k
		
		// 读取每个战士的m个属性
		vector<vector<int>> A(n, vector<int>(m));
		for(auto &row: A){
			for(auto &x: row){
				cin >> x;
			}
		}
		
		// 二分查找的范围为属性值的最小值1到最大值1000
		int left = 1, right = 1000, res = 0;
		
		while(left <= right){
			int mid = left + (right - left) / 2; // 取中间值作为当前尝试的战斗力
			
			// 统计每种掩码出现的次数
			// 掩码表示战士覆盖的属性集合
			vector<int> freq(1 << m, 0);
			for(int i = 0; i < n; i++){
				int mask = 0;
				for(int j = 0; j < m; j++) {
					if(A[i][j] >= mid){
						mask |= (1 << j); // 如果第j个属性值 >= mid，则在掩码中置位
					}
				}
				if(mask != 0){
					freq[mask]++; // 统计该掩码出现的次数
				}
			}
			
			// 位掩码动态规划
			// dp[mask] 表示覆盖mask所需的最少人数
			vector<int> dp(1 << m, INF);
			dp[0] = 0; // 覆盖空集需要0人
			
			for(int mask = 0; mask < (1 << m); mask++){
				if(dp[mask] >= k) continue; // 如果当前覆盖mask所需人数已超过k，跳过
				for(int sub_mask = 1; sub_mask < (1 << m); sub_mask++){
					if(freq[sub_mask] == 0) continue; // 如果没有战士对应该子掩码，跳过
					int new_mask = mask | sub_mask; // 合并当前mask和子掩码
					dp[new_mask] = min(dp[new_mask], dp[mask] + 1); // 更新覆盖new_mask所需的最少人数
				}
			}
			
			int full_mask = (1 << m) - 1; // 全部属性的掩码
			if(dp[full_mask] <= k){
				res = mid; // 当前mid可行，尝试更大的值
				left = mid + 1;
			}
			else{
				right = mid - 1; // 当前mid不可行，尝试更小的值
			}
		}
		
		cout << res << "\n"; // 输出最大战斗力
	}
}

python

INF = int(1e9)  # 定义一个足够大的常数，用于初始化DP数组

def main():
    T = int(input())  # 测试数据组数
    
    while T > 0:
        T -= 1
        
        # 读取候选人数量n，属性数量m，选择人数k
        n, m, k = map(int, input().split())
        
        # 读取每个战士的m个属性
        A = [list(map(int, input().split())) for _ in range(n)]
        
        # 二分查找的范围为属性值的最小值1到最大值1000
        left, right, res = 1, 1000, 0
        
        while left <= right:
            mid = (left + right) // 2  # 取中间值作为当前尝试的战斗力
            
            # 统计每种掩码出现的次数
            # 掩码表示战士覆盖的属性集合
            freq = [0] * (1 << m)
            for i in range(n):
                mask = 0
                for j in range(m):
                    if A[i][j] >= mid:
                        mask |= (1 << j)  # 如果第j个属性值 >= mid，则在掩码中置位
                if mask != 0:
                    freq[mask] += 1  # 统计该掩码出现的次数
            
            # 位掩码动态规划
            # dp[mask] 表示覆盖mask所需的最少人数
            dp = [INF] * (1 << m)
            dp[0] = 0  # 覆盖空集需要0人
            
            for mask in range(1 << m):
                if dp[mask] >= k:
                    continue  # 如果当前覆盖mask所需人数已超过k，跳过
                for sub_mask in range(1, 1 << m):
                    if freq[sub_mask] == 0:
                        continue  # 如果没有战士对应该子掩码，跳过
                    new_mask = mask | sub_mask  # 合并当前mask和子掩码
                    dp[new_mask] = min(dp[new_mask], dp[mask] + 1)  # 更新覆盖new_mask所需的最少人数
            
            full_mask = (1 << m) - 1  # 全部属性的掩码
            if dp[full_mask] <= k:
                res = mid  # 当前mid可行，尝试更大的值
                left = mid + 1
            else:
                right = mid - 1  # 当前mid不可行，尝试更小的值
        
        print(res)  # 输出最大战斗力

if __name__ == '__main__':
    main()

java

import java.util.*;

public class Main {
    static final int INF = (int) 1e9; // 定义一个足够大的常数，用于初始化DP数组

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt(); // 测试数据组数
        
        while (T-- > 0) {
            int n = sc.nextInt(); // 读取候选人数量n
            int m = sc.nextInt(); // 读取属性数量m
            int k = sc.nextInt(); // 选择人数k
            
            // 读取每个战士的m个属性
            int[][] A = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    A[i][j] = sc.nextInt();
                }
            }
            
            // 二分查找的范围为属性值的最小值1到最大值1000
            int left = 1, right = 1000, res = 0;
            
            while (left <= right) {
                int mid = left + (right - left) / 2; // 取中间值作为当前尝试的战斗力
                
                // 统计每种掩码出现的次数
                // 掩码表示战士覆盖的属性集合
                int[] freq = new int[1 << m];
                for (int i = 0; i < n; i++) {
                    int mask = 0;
                    for (int j = 0; j < m; j++) {
                        if (A[i][j] >= mid) {
                            mask |= (1 << j); // 如果第j个属性值 >= mid，则在掩码中置位
                        }
                    }
                    if (mask != 0) {
                        freq[mask]++; // 统计该掩码出现的次数
                    }
                }
                
                // 位掩码动态规划
                // dp[mask] 表示覆盖mask所需的最少人数
                int[] dp = new int[1 << m];
                Arrays.fill(dp, INF);
                dp[0] = 0; // 覆盖空集需要0人
                
                for (int mask = 0; mask < (1 << m); mask++) {
                    if (dp[mask] >= k) continue; // 如果当前覆盖mask所需人数已超过k，跳过
                    for (int sub_mask = 1; sub_mask < (1 << m); sub_mask++) {
                        if (freq[sub_mask] == 0) continue; // 如果没有战士对应该子掩码，跳过
                        int new_mask = mask | sub_mask; // 合并当前mask和子掩码
                        dp[new_mask] = Math.min(dp[new_mask], dp[mask] + 1); // 更新覆盖new_mask所需的最少人数
                    }
                }
                
                int full_mask = (1 << m) - 1; // 全部属性的掩码
                if (dp[full_mask] <= k) {
                    res = mid; // 当前mid可行，尝试更大的值
                    left = mid + 1;
                } else {
                    right = mid - 1; // 当前mid不可行，尝试更小的值
                }
            }
            
            System.out.println(res); // 输出最大战斗力
        }
    }
}

题目内容

小红的集训队共有 $n$ 个人，每个人都有 $m$ 个属性，现在需要挑选其中的 $k$ 个人组成战队出战。

战队也有 $m$ 个属性，这些属性的计算方式是，挑选出的 $k$ 个人里该属性的最大值。

由于“木桶理论”（一只木桶能装多少水取决于它最短的那块木板），战队的战斗力，取决于这个战队的 $m$ 个属性里的那个最小值。

问如何挑选队员，可以使得战队的战斗力最强，请输出战队的最高战斗力。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1≤T≤100)$，代表数据组数，每组测试数据描述如下：

第一行三个整数 $n,m,k(1≤n≤3×10^5 ;1≤m≤10 ；1≤k≤n)$。代表候选人量、属性数量、站队需要的总人数。

接下来 $n$ 行，每行输入 $m$ 个整数，$a_1,a_2,...,a_m(1≤a_i≤10^3)$代表每一位战士的 $m$ 项属性。

除此之外，保证全部测试数据的 $n×m$ 之和不超过 $3×10^5$。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表候选人能组成的站队的最大总战斗力。

样例1

输入

1
3 5 3
3 9 6 4 6
6 9 3 1 1
8 8 9 3 7

输出

4

样例2

输入

1
5 2 2
1 6
2 6
3 7
4 3 
5 2

输出

5