网易互娱 研发 2019-9-14 第二题两两组队匹配

import java.util.Scanner;

class newUser{
    private int id;
    private int better=0;//匹配过几位老用户
    private int[] rank=null;//新用户对老用户偏好
    private boolean match=false;
    private int present=0;
    public int getBetter() {
        return better;
    }
    public void setBetter(int better) {
        this.better = better;
    }
    public int getPresent() {
        return present;
    }
    public void setPresent(int present) {
        this.present = present;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public int[] getRank() {
        return rank;
    }
    public void setRank(int[] rank) {
        this.rank = rank;
    }
    public boolean isMatch() {
        return match;
    }
    public void setMatch(boolean match) {
        this.match = match;
    }
    public String toString() {
        return this.getId()+" "+this.getPresent();
    }
}
class oldUser{
    private int id;
    private int[] rank=null;//老用户对新用户偏好
    private boolean match=false;
    private int present=0;
    public int getPresent() {
        return present;
    }
    public void setPresent(int present) {
        this.present = present;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public int[] getRank() {
        return rank;
    }
    public void setRank(int[] rank) {
        this.rank = rank;
    }
    public boolean isMatch() {
        return match;
    }
    public void setMatch(boolean match) {
        this.match = match;
    } 
    public String toString() {
        return this.getId()+" "+this.getPresent();
    }
}

/**
 *
 稳定匹配算法:为新用户匹配老用户
 输入:
 3
 1 2 3 1
 2 1 3 2
 3 1 2 3
 1 1 2 3
 2 1 2 3
 3 1 2 3
 输出:
 1 2
 2 1
 3 3
 */
public class NeteaseMain_用户匹配 {
    public static newUser newuser[]=null;
    public static oldUser olduser[]=null;
    public static int n;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        newuser=new newUser[n];
        olduser=new oldUser[n];
        for(int i=0;i<n;i++){
            newUser ne=new newUser();
            ne.setId(sc.nextInt());
            int rank[]=new int[n];
            for(int j=0;j<n;j++){
                rank[j]=sc.nextInt();
            }
            ne.setRank(rank);
            newuser[i]=ne;
        }

        for(int i=0;i<n;i++){
            oldUser old=new oldUser();
            old.setId(sc.nextInt());
            int rank[]=new int[n];
            for(int j=0;j<n;j++){
                rank[j]=sc.nextInt();
            }
            old.setRank(rank);
            olduser[i]=old;
        }
        //System.out.println(newuser[0].getRank().toString());
        newUser theNew=null;
        while((theNew=findNewUser(newuser))!=null){//循环找出新用户列表中找出还未匹配的新用户
            allocate(theNew,olduser);//为新用户分配老用户
        }
        for(int i=0;i<n;i++){
            System.out.println(newuser[i]);
        }
    }

    /**
     * 找出新用户中未还匹配的新用户
     * @param newusers
     * @return */
    public static newUser findNewUser(newUser[] newusers){
        for(int i=0;i<newusers.length;i++){
            if(!newusers[i].isMatch()){
                return newusers[i];
            }
        }
        return null;
    }

    /**
     * 为新用户分配老用户
     * @param m
     * @param oldUsers
     */
    public static void allocate(newUser m,oldUser[] oldUsers){
        oldUser w=oldUsers[m.getRank()[m.getBetter()]-1];//新用户m对老用户的偏好列表中最偏好的老用户
        if(!w.isMatch()){//若老用户为被分配
                match(m,w);
        }else{
            if(pk(m,w)){//若m和老用户当前分配的新用户Pk成功
                match(m,w);
            }else{
                m.setBetter(m.getBetter()+1);//前任排行下降
            }
        }
    }

    public static void match(newUser m,oldUser w){
        if(!w.isMatch()){
            m.setMatch(true);
            m.setPresent(w.getId());
            w.setMatch(true);
            w.setPresent(m.getId());
        }
        else{//更换
            m.setMatch(true);
            m.setPresent(w.getId());
            newuser[w.getPresent()].setMatch(false);
            newuser[w.getPresent()].setPresent(0);
            w.setPresent(m.getId());
        }
    }

    public static boolean pk(newUser m,oldUser w){
        int former=0;//前任排行
        for(int i=0;i<n;i++){
            if(w.getRank()[i]==w.getPresent()){
                former=i;
                break;
            }
        }
        int later=0;//挑战者排行
        for(int i=0;i<n;i++){
            if(w.getRank()[i]==m.getId()){
                later=i;
                break;
            }
        }
        if(later<former){
            return true;
        }else {
            return false;
        }
    }
}