蓝桥杯算法提高VIP-士兵排队问题-题解(Java代码) 显示错误27%，但在蓝桥官网是可以全部通过的

660 阅读 2 评论 0 点赞

###主要考的拓扑排序的

#####举个例子：这边可以将1-26看成A-Z,图1的1  3对应题目中的A> C,转化一下就好了，这边说下思路 具体的可以网上看下拓扑排序的其他优化和解法（如要生成字典序列最小的）
![](/image_editor_upload/20200309052721_14321.jpg)

****比如输入如图一，第二步转化成图二的邻接表，此时被指向的数的入度+1，此时1  3的话，图三中数字3下面的值+1，处理完各个数字的入度如图三，

上面就是数据的处理，接下来入度为0的数字入队(没参加的不算) 这边就是1 2
1：当队列不空的时候
2：出队头元素，并将其邻接表后的数字的入度-1，若减为了0，加入队列
3；重复第2步，直到队列为空

结果的判断：怎么判断其有没有解，这边我们可以用两个计数的变量，我以下是count1记录参加排身高的个数  count2记录输出个数
若count1!=count2 证明出现了环的情况，结果就是无解  如A>B  B>A
否则  输出结果

这个在蓝桥官网是可以全部通过的，这边不知道怎么回事

```java
package pratice;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class _拓扑排序_邻接表
{

public static void main(String[] args)
	{
		Scanner scan=new Scanner(System.in);
		
		Node6[] node=new Node6[27];
		int[] book=new int[27];//标记字母有没有参加
		
		int[] R=new int[27];//存储入度
		
		
		
		for(int i=1;i<=26;i++)
		{
			
			node[i]=new Node6(i);//这边就是直接先实例化了A-Z
			
		}
		
		while(scan.hasNextLine())
		{
			String s=scan.nextLine();
			if(s.isEmpty())
				break;
			int flag=0;
			char a = 0;
			char b = 0;
			//char a=s.charAt(0);
			//char b=s.charAt(3);
			//原本应该是可以直接截取获得a b,但这边数据可能有点不一样，就用了一下的方式
			for(int i=0;i<s.length();i++)
			{
				if(s.charAt(i)>='A'&&s.charAt(i)<='Z'&&flag==0)
				{
					a=s.charAt(i);
					flag=1;
				}
				else if(s.charAt(i)>='A'&&s.charAt(i)<='Z'&&flag==1)
				{
					b=s.charAt(i);
					break;
				}
					
			}
			
			
			node[a-'A'+1].list.add(b-'A'+1);//进行关联，并且关联的数入度加1
			
			R[(b-'A'+1)]++;
			book[a-'A'+1]=1;
			book[b-'A'+1]=1;
		}
		
		Queue<Node6> queue=new LinkedList<>();
		
		for(int i=1;i<=26;i++)
		{
			if(R[i]==0&&book[i]==1)
				queue.offer(node[i]);
		}
		
		List<Integer> list;
		//判断有几个字符
		int count1=0;
		for(int i=1;i<=26;i++)
		{
			if(book[i]==1)
				count1++;
		}
		
		List<Character> list2=new ArrayList<Character>();
		int count2=0;
		
		while(!queue.isEmpty())
		{
			Node6 tnode=queue.poll();
			
			//System.out.print((char)(tnode.value+'A'-1));
			list2.add((char)(tnode.value+'A'-1));
			count2++;
			
			list=tnode.getList();
			for(int i=0;i<list.size();i++)
			{
				R[list.get(i)]--;
				if(R[list.get(i)]==0)
					queue.add(node[list.get(i)]);
			}
		}
		
		if(count1!=count2)
			System.out.println("No Answer!");
		else
		{
			for(int i=0;i<list2.size();i++)
				System.out.print(list2.get(i));
		}
		
 		
		
		scan.close();

}

}
//java 构造邻接表
class Node6
{
	int value;//值
	List<Integer> list;
	
	public Node6(int value)
	{
		this.value=value;
		list=new ArrayList<Integer>();
	}
	
	public List<Integer> getList()
	{
		return list;
		
	}
	
	public void setList(List<Integer> list)
	{
		this.list=list;
	}
	
	
}

```

0.0分

3 人评分

本文分类：题解列表
浏览次数：660 次浏览
发布日期：2020-03-09 17:49:52
本文链接：https://blog.dotcpp.com/a/67692

上一篇 > [编程入门]筛选N以内的素数-题解(C++代码)
下一篇 > [编程入门]数字的处理与判断-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 2 条评论

万卷消永愁 4年前回复TA

这个题就是个坑，首先拓扑排序本身就很可能有不唯一答案，每次刷新找到入度为0的输出（入度为0的有多个的时候也没有规定先输出哪一个，一般是按顺序来的）。这里题目给的测试数据也很奇怪，还有重复的读入，读入顺序也有矛盾的地方，有的测试数据是优先找入读为0且出度也为0的输出，有的是在出度都不为0的时候，先找字母大的，也有先找字母小的，真是搞不懂。希望大家刷这个题适可而止，思路很简单的，不用死磕。

renqinghua 4年前回复TA

将64行改成 Queue<Node6> queue=new PriorityQueue<>(cmp);可以得到字典序最小的排列
       //自定义比较器
	static Comparator<Node6> cmp=new Comparator<Node6>()
	{

			@Override
			public int compare(Node6 o1, Node6 o2)
			{
				return o1.value-o2.value;//字典序小
				//return o2.value-o1.value;//字典序大
			}
		
	};

蓝桥杯算法提高VIP-士兵排队问题-题解(Java代码) 显示错误27%，但在蓝桥官网是可以全部通过的

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 2 条评论

发表评论 取消回复

评论列表共有 2 条评论

发表评论取消回复