看算法的时候遇到一个题目：
两个乒乓球队进行比赛，各出三人。A队为a,b,c三人，B队为x,y,z三人。
已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队 赛手的名单。 现在把自己写好的代码发上来，看大家有没有更好的建议和意见。
package com.codeWrite;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class FindOpponent {
/**
两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。
已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。
*/
List<TeamA> teamA =new ArrayList<TeamA>(); //用来存放A组的列表
List<TeamB> teamB =new ArrayList<TeamB>(); //用来存放B组的列表
List<Team> team =new ArrayList<Team>(); //所有队员的列表
Map<TeamA,TeamB> map =new HashMap<TeamA,TeamB>();//用来存放比赛对阵名单
public void arrangeMatch(){
/*如何安排比赛的判断条件就是：在不违反当前队员的比赛条件前提下，同时与其他有比赛条件的队员之间不能发生冲突而且应该从限制条件多的队员开始进行考虑，因为限制越多其能选择的对手就越少，所以优先考虑。
*/
while(team.size()>0){
if(team.get(0) instanceof TeamA){//从队员列表的第一个队员开始遍历
TeamA eachA =(TeamA)team.get(0);
if(eachA.list!=null){// 如果这个队员有限制条件的话
List<TeamB> copyTeamB=cloneList(teamB); //将B组的队员列表复制一份
teamB.removeAll(eachA.list);//将B组中不符合当前队员的条件剔除掉
for(TeamB eachB:teamB){ //进行互斥判断
if(canArrange(eachA,eachB)){//如果两者可以互为对手的话
eachA.t=eachB; //相互为对手
eachB.t=eachA;
teamA.remove(eachA); //安排好的队员将被删除
copyTeamB.remove(eachB); //将复制过去的列表中删除掉选中队员
teamB =copyTeamB; //并将修改后的列表重新复制给teamB
team.remove(eachA);//并将队员列表中已经安排好的队员去掉
team.remove(eachB);
map.put(eachA, eachB);
}
}
}
}
/*更科学的写法这儿应该还有个对B组队员的比赛安排，如果B组队员也有限制条件的话那么队员 列表中的队员顺序就应该是不同组的队员混乱排列
*/
}
}
public void initial(){ //该方法对参赛队员和限制条件进行初始化
TeamA a =new TeamA();
TeamA b =new TeamA();
TeamA c =new TeamA();
TeamB x =new TeamB();
TeamB y =new TeamB();
TeamB z =new TeamB();
a.name="a";
b.name="b";
c.name="c";
x.name="x";
y.name="y";
z.name="z";
a.list.add(x);
c.list.add(x);
c.list.add(z);
//这儿最好有个能对限制条件的多少进行降序排序的过程，因为分析所得，需要对限制条件多的队友优先进行比赛的安排
teamA.add(c);
teamA.add(a);
teamA.add(b);
teamB.add(x);
teamB.add(y);
teamB.add(z);
team.addAll(teamA);
team.addAll(teamB);
}
public List<TeamB> cloneList(List<TeamB> list){ //复制一个数组中的元素到另外一个临时数组中
List<TeamB> newList =new ArrayList<TeamB>();
for(int i=0;i<list.size();i++){
newList.add(list.get(i));
}
return newList;
}
public boolean canArrange(TeamA a,TeamB b){ //对两名队员进行互斥判定，是否能够互为对手
boolean aVSb =false;
boolean bVSa =false;
if(a.list!=null){
a.list.contains(b);
aVSb=true;
}
if(b.list!=null){
b.list.contains(a);
bVSa=true;
}
if(aVSb&bVSa){
return true;
}else{
return false;
}
}
public void iteMap(Map<TeamA,TeamB> map){ //打印对阵表
Set<Map.Entry<TeamA,TeamB>> set =map.entrySet();
for(Map.Entry<TeamA, TeamB> each: set){
System.out.print(each.getKey().name+"对阵"+each.getValue().name+'\n');
}
}
public static void main(String[] args) {
FindOpponent fo =new FindOpponent();
fo.initial();
fo.arrangeMatch();
fo.iteMap(fo.map);
}
}
interface Team{
}
class TeamA implements Team{
String name; //队员名字
TeamB t; //对手
List<TeamB> list=new ArrayList<TeamB>();//用来存放不与之比赛的对手列表
}
class TeamB implements Team{
String name;
TeamA t;
List<TeamA> list=new ArrayList<TeamA>();
}
|
|
收藏
淘帖
踩
