本文主要是介绍【华为机试题】黑白棋子的最大匹配度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
棋盘上有黑白两种颜色的棋子，选出一对黑白棋子，若黑棋的横坐标小于等于白棋的横坐标，黑棋的纵坐标小于等于白棋的纵坐标，则称这一对棋子为匹配。求任意个数的黑白棋中最佳匹配的对数。输入：
测试用例数
对每一组测试用例的输入如下：
黑棋个数，白棋个数
黑棋的横纵坐标白棋的横纵坐标
输入示例：
2 //测试用例数
2 2//第一组黑棋和白棋的个数
0 1//第一组黑棋的第一个棋子坐标
1 1//第一组黑棋的第二个棋子坐标
1 1//第一组白棋的第一个棋子坐标
1 2//第一组白棋的第二个棋子坐标
1 1//第二组测试用例黑棋和白棋个数
0 0//第二组黑棋坐标
0 0//第二组白棋坐标
输出：
2
1思想：采用全排列的思想来做，将黑棋和白棋中个数多的一个做全排列，针对每一次排列，选取与少者个数相同的个数进行比较，比较结果即为本次排列的匹配度，用一个变量保存最大的匹配度，当完成一次全排列即可求出最大匹配值。
代码：
#include<iostream>
#include<vector>
using namespace std;
struct Pos{int x;int y;
};
int maxMatchNum=0;
int countTheMatchNum(vector<Pos>& black_chess,vector<Pos>& white_chess){int matchNum=0;int size1=black_chess.size();int size2=white_chess.size();int len=size1<size2?size1:size2;for(int i=0;i<len;i++){if(black_chess[i].x<=white_chess[i].x&&black_chess[i].y<=white_chess[i].y)matchNum++;}return matchNum;
}
void Permutation(vector<Pos>& black_chess,vector<Pos>& white_chess,vector<Pos>::iterator begin,vector<Pos>::iterator end){if(begin==end){int matchNum=countTheMatchNum(black_chess,white_chess);if(maxMatchNum<matchNum){maxMatchNum=matchNum;return;}}else{for(auto itr=begin;itr<end;itr++){Pos temp = *itr;*itr = *begin;*begin = temp;Permutation(black_chess,white_chess,begin+1,end);temp =*itr;*itr = *begin;*begin = temp;}}
}
void countTheBestMatchNum(vector<Pos>& black,vector<Pos>& white){if(black.size()>=white.size())Permutation(black,white,black.begin(),black.end());else Permutation(black,white,white.begin(),white.end());
}
int main(void){int test_num;cin>>test_num;while(test_num--){int m,n;cin>>m>>n;vector<Pos> black;vector<Pos> white;for(int i=0;i<m;i++){Pos point;cin>>point.x>>point.y;black.push_back(point);}for(int i=0;i<n;i++){Pos point;cin>>point.x>>point.y;white.push_back(point);}countTheBestMatchNum(black,white);cout<<maxMatchNum<<endl;maxMatchNum=0;}system("pause");return 0;
}
这篇关于【华为机试题】黑白棋子的最大匹配度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
