原文链接: https://leetcode-cn.com/problems/maximum-compatibility-score-sum
英文原文
There is a survey that consists of n questions where each question's answer is either 0 (no) or 1 (yes).
The survey was given to m students numbered from 0 to m - 1 and m mentors numbered from 0 to m - 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the ith student (0-indexed). The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the jth mentor (0-indexed).
Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.
- For example, if the student's answers were
[1, 0, 1]and the mentor's answers were[0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.
You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.
Given students and mentors, return the maximum compatibility score sum that can be achieved.
Example 1:
Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]] Output: 8 Explanation: We assign students to mentors in the following way: - student 0 to mentor 2 with a compatibility score of 3. - student 1 to mentor 0 with a compatibility score of 2. - student 2 to mentor 1 with a compatibility score of 3. The compatibility score sum is 3 + 2 + 3 = 8.
Example 2:
Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]] Output: 0 Explanation: The compatibility score of any student-mentor pair is 0.
Constraints:
m == students.length == mentors.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k]is either0or1.mentors[j][k]is either0or1.
中文题目
有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。
这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i] 是一个整数数组，包含第 i 名学生对调查问卷给出的答案（下标从 0 开始）。导师的答案用一个二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，包含第 j 名导师对调查问卷给出的答案（下标从 0 开始）。
每个学生都会被分配给 一名 导师，而每位导师也会分配到 一名 学生。配对的学生与导师之间的兼容性评分等于学生和导师答案相同的次数。
- 例如，学生答案为
[1, 0, 1]而导师答案为[0, 0, 1]，那么他们的兼容性评分为 2 ，因为只有第二个和第三个答案相同。
请你找出最优的学生与导师的配对方案，以 最大程度上 提高 兼容性评分和 。
给你 students 和 mentors ，返回可以得到的 最大兼容性评分和 。
示例 1：
输入：students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]] 输出：8 解释：按下述方式分配学生和导师： - 学生 0 分配给导师 2 ，兼容性评分为 3 。 - 学生 1 分配给导师 0 ，兼容性评分为 2 。 - 学生 2 分配给导师 1 ，兼容性评分为 3 。 最大兼容性评分和为 3 + 2 + 3 = 8 。
示例 2：
输入：students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]] 输出：0 解释：任意学生与导师配对的兼容性评分都是 0 。
提示：
m == students.length == mentors.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k]为0或1mentors[j][k]为0或1
通过代码
高赞题解
最大兼容性评分和 - 力扣 (LeetCode) 竞赛
第三道题。
题目说通过做题的选择情况，每个学生和每个老师直接都有一定的匹配度，求匹配方案最佳时最大匹配度是多少。
乍一看感觉是要写匹配什么的，看了看数据量果断暴力搜索。
class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
m = students.size();
n = (*(students.begin())).size();
for(int i = 0; i < m; ++i){
for(int j = 0; j < m; ++j){ //遍历，记录每个学生和每个老师的匹配度
cost[i][j] = 0;
for(int k = 0; k < n; ++k){
cost[i][j] += students[i][k] == mentors[j][k] ? 1 : 0;
} //cost[i][j]是学生i和老师j的匹配度
}
}
ans = 0;
for(int i = 0; i < m; ++i){
memset(flag, false, sizeof(flag)); //每个学生还没有开始选老师
DFS(i, 0, 0);
}
return ans;
}
private:
int cost[8][8]; //记录匹配度
bool flag[8]; //记录老师是否已经被匹配
int m, n;
int ans;
void DFS(int th, int row, int dev){ //th是选中的老师，row是当前正在选的学生
dev += cost[row][th];
if(row == m - 1){ //如果已经每个都匹配好了
ans = max(ans, dev); //返回当前匹配度
return;
}
flag[th] = true; //这个老师被选中了
for(int i = 0; i < m; ++i){
if(!flag[i]){
DFS(i, row + 1, dev); //第row + 1的学生从所有没有被选中的老师里选一个
flag[i] = false; //退出DFS的时候记得把刚刚选中的老师标记回false（未被选中）
}
}
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 4221 | 7710 | 54.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
