每个测试文件仅有一条测试数据。 第一行输入M,N,分别表示男同学的数量,女同学的数量。(1<=M<=100,1<=N<=100) 第二行输入M个正整数,分别表示男同学们的颜值。 第三行输入N个正整数,分别表示女同学们的颜值。 注意,所有人的颜值分数范围在[1,100] Java实现
时间: 2024-03-30 22:36:49 浏览: 15
好的,根据你提供的问题描述,我来给出具体的Java实现。
算法实现:
```
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int M = scan.nextInt();
int N = scan.nextInt();
int[] boys = new int[M];
int[] girls = new int[N];
for (int i = 0; i < M; i++) {
boys[i] = scan.nextInt();
}
for (int i = 0; i < N; i++) {
girls[i] = scan.nextInt();
}
int[][] graph = new int[M][N];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (boys[i] == girls[j] || boys[i] > girls[j]) {
graph[i][j] = 1;
}
}
}
int[] match = new int[N];
Arrays.fill(match, -1);
int ans = 0;
for (int i = 0; i < M; i++) {
boolean[] vis = new boolean[N];
if (dfs(i, graph, match, vis)) {
ans++;
}
}
System.out.println(ans);
scan.close();
}
public static boolean dfs(int u, int[][] graph, int[] match, boolean[] vis) {
int n = graph[0].length;
for (int i = 0; i < n; i++) {
if (graph[u][i] == 1 && !vis[i]) {
vis[i] = true;
if (match[i] == -1 || dfs(match[i], graph, match, vis)) {
match[i] = u;
return true;
}
}
}
return false;
}
}
```
代码解析:
1. 读入输入数据,分别存储男生、女生的颜值。
2. 根据颜值构建二分图,即男生和女生之间的关系。
3. 使用匈牙利算法求解最大匹配数。
4. 输出最大匹配数即可。
时间复杂度分析:
构建二分图的时间复杂度为 $O(MN)$,匈牙利算法的时间复杂度为 $O(MN)$,因此总时间复杂度为 $O(MN)$。空间复杂度为 $O(MN)$。