Java实现蓝桥杯VIP 算法提高士兵排队问题

算法提高士兵排队问题
时间限制：1.0s 内存限制：256.0MB
试题
　　有Ｎ个士兵(1≤Ｎ≤26)，编号依次为Ａ,Ｂ,Ｃ,…，队列训练时，指挥官要把一些士兵从高到矮一次排成一行，但现在指挥官不能直接获得每个人的身高信息，只能获得“P1比P2高”这样的比较结果(P1、P2∈Ａ,Ｂ,Ｃ,…,Ｚ,记为 P1>P2)，如”Ａ>Ｂ”表示Ａ比Ｂ高。
　　请编一程序，根据所得到的比较结果求出一种符合条件的排队方案。
　　（注：比较结果中没有涉及的士兵不参加排队）
输入要求
　　比较结果从文本文件中读入（文件由键盘输入），每个比较结果在文本文件中占一行。
输出要求
　　若输入数据无解，打印“No Answer!”信息，否则从高到矮一次输出每一个士兵的编号，中间无分割符，并把结果写入文本文件中，文件由键盘输入：
样例输入
A>B
B>D
F>D
样例输出
AFBD

import java.util.LinkedList;
import java.util.Scanner;


public class 士兵排列问题 {//这道题的输入是文件输入，
	                     //与手动输入有些不一样
	 					//自己可以稍微改一下看看测试用例
	static boolean[] visit = new boolean[26];
	static boolean[][] dep = new boolean[26][26];
	static int[] in = new int[26];
	static char[] ans = new char[26];
	
	public static void topSort(){//拓扑排序
		LinkedList<Integer> q = new LinkedList<Integer>();
		int n = 0;
		for(int i=0;i<26;++i){
			if(visit[i] == true){
				n++;
				if(in[i] == 0)
					q.add(i);
			}
		}
		
		int index = 0;
		while(!q.isEmpty()){
			//队列首元素出队列
			int f = q.pollFirst();
			n--;
			ans[index++] = (char) (f + 'A');
			for(int i=0;i<26;++i){
				if(visit[i] && dep[f][i]){
					in[i]--;
					if(in[i] == 0)
						q.add(i);
				}
			}
		}
		if(n != 0){
			System.out.println("No Answer!");
		}else{
			for(int i=0;i<index;++i){
				System.out.print(ans[i]);
			}
		}
	}
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	char a,op,b;
    	int x,y;
    	//int count = 0;
        while(sc.hasNext()){
        	
        	String str = sc.nextLine();
        	//count++;
         	char[] arr = str.toCharArray();
         	a=arr[0];
         	op=arr[1];
         	b=arr[2];
         	x = a-'A';
         	y = b-'A';
         	visit[x] = visit[y] = true;
         	if(dep[x][y] == false){
         		dep[x][y] = true;
         		in[y]++;
         	}
         	
        }
    	topSort();
    }

}

import java.util.LinkedList;
import java.util.Scanner;


public class 士兵排列问题 {//这道题的输入是文件输入，
	                     //与手动输入有些不一样
	 					//自己可以稍微改一下看看测试用例
	static boolean[] visit = new boolean[26];
	static boolean[][] dep = new boolean[26][26];
	static int[] in = new int[26];
	static char[] ans = new char[26];
	
	public static void topSort(){//拓扑排序
		LinkedList<Integer> q = new LinkedList<Integer>();
		int n = 0;
		for(int i=0;i<26;++i){
			if(visit[i] == true){
				n++;
				if(in[i] == 0)
					q.add(i);
			}
		}
		
		int index = 0;
		while(!q.isEmpty()){
			//队列首元素出队列
			int f = q.pollFirst();
			n--;
			ans[index++] = (char) (f + 'A');
			for(int i=0;i<26;++i){
				if(visit[i] && dep[f][i]){
					in[i]--;
					if(in[i] == 0)
						q.add(i);
				}
			}
		}
		if(n != 0){
			System.out.println("No Answer!");
		}else{
			for(int i=0;i<index;++i){
				System.out.print(ans[i]);
			}
		}
	}
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	char a,op,b;
    	int x,y;
    	//int count = 0;
        while(sc.hasNext()){
        	
        	String str = sc.nextLine();
        	//count++;
         	char[] arr = str.toCharArray();
         	a=arr[0];
         	op=arr[1];
         	b=arr[2];
         	x = a-'A';
         	y = b-'A';
         	visit[x] = visit[y] = true;
         	if(dep[x][y] == false){
         		dep[x][y] = true;
         		in[y]++;
         	}
         	
        }
    	topSort();
    }

}

Java实现 蓝桥杯VIP 算法提高 士兵排队问题

相关推荐

Java实现蓝桥杯VIP 算法提高士兵排队问题