首页 > 代码库 > 拓扑排序——烦人的幻灯片
拓扑排序——烦人的幻灯片
烦人的幻灯片
Description
李教授于今天下午做一个非常重要的演讲。不幸的是他不是一个非常爱整洁的人，他把自己做演讲要用的幻灯片随便堆放在一起。因此，演讲之前他不得不去整理这些幻灯片。做为一个讲求效率的学者，他希望尽可能简单地完成它。情况是这样，教授这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1，2，…，n在上面编上了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。现在我们用大写字母A，B，C，。。。再次把幻灯片依次编上号，如样例所示，我们可以很快发现编号为A的幻灯片是第4张，把它抽出来后我们又可以确定编号为C的幻灯片是第2张，。。。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若是出现多种对应的情况或是某些数字编号和字母对应不起来，我们就称对应是无法实现的。
Input
第一行只有一个数n，表示有n张幻灯片，接下来的n行第行包括4个整数Xmin，Xmax，Ymin，Ymax（整数之间用空格分开），为幻灯片的坐标（该区域为幻灯片），这n张幻灯片按其在输入文件中出现的顺序从前到后依次编号为A，B，C，。。。再接下来的n行依次为n个数字编号的坐标X，Y，显然在幻灯片之外是不会有数字的。
Output
若是对应可以实现，你的输出应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且各行以字母的升序排列，注意输出的字母要大写并且顶格；反之，若是对应无法实现，在文件的第一行顶格输出None即可。行首行末无多余空格。
Sample Input
46 22 10 204 18 6 168 20 2 1810 24 4 89 1519 1711 721 11
Sample Output
A 4B 1C 2D 3
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn=100; 7 int n; 8 struct node { 9 int xmin;10 int xmax;11 int ymin;12 int ymax;13 int x;14 int y;15 }a[maxn],b[maxn];16 17 int y1[maxn],x1[maxn];18 19 bool bianjie(int x,int y,int x1,int x2,int y1,int y2)20 {21 if(x>=x1&&x<=x2&&y>=y1&&y<=y2)22 return 1;23 return 0; 24 }25 26 int main()27 {28 while(cin>>n)29 {30 for(int i=1;i<=n;i++)31 {32 cin>>a[i].xmin>>a[i].xmax>>a[i].ymin>>a[i].ymax;33 }34 for(int i=1;i<=n;i++)35 {36 cin>>b[i].x>>b[i].y;37 }38 int m=n;39 memset(x1,0,sizeof(x1));40 memset(y1,0,sizeof(y1));41 int cnt=0;42 while(m--)43 {44 for(int i=1;i<=n;i++)45 {46 if(y1[i]) continue;47 int flag=0,temp; 48 for(int j=1;j<=n;j++)49 {50 if(x1[j]) continue;51 if(bianjie(b[i].x,b[i].y,a[j].xmin,a[j].xmax,a[j].ymin,a[j].ymax))52 {53 temp=j;54 flag++;55 }56 }57 if(flag==1)58 {59 x1[temp]=i;60 y1[i]=temp;61 cnt++;62 }63 }64 }65 if(cnt!=n)66 {67 cout<<"None"<<endl;68 continue;69 }70 for(int i=1;i<=n;i++)71 cout<<char(i+64)<<" "<<x1[i]<<endl;72 }73 return 0;74 }
拓扑排序——烦人的幻灯片
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。