A28837. 烦人的幻灯片(slides)
填空题
困难
知识点
题目描述
烦人的幻灯片(slides)
题目描述
李教授将于今天下午作一次非常重要的演讲。不幸的事他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1~n编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。
现在我们用大写字母A,B,C……再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。
输入
第一行只有一个整数n，表示有n张幻灯片，接下来的n行每行包括4个整数xmin,xmax,ymin,ymax（整数之间用空格分开）为幻灯片的坐标，这n张幻灯片按其在文件中出现的顺序从前到后依次编号为A,B,C……，再接下来的n行依次为n个数字编号的坐标x,y，显然在幻灯片之外是不会有数字的。
输出
若是对应可以实现，输出文件应该包括n行，每一行为一个字母和一个数字，中间以一个空格隔开，并且每行以字母的升序排列，注意输出的字母要大写并且定格；反之，若是对应无法实现，在文件的第一行顶格输出None即可。首行末无多余的空格。
输入样例
4
6 22 10 20
4 18 6 16
8 20 2 18
10 24 4 8
9 15
19 17
11 7
21 11输出样例
A 4
B 1
C 2
D 3参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 30
struct Rect
{
int xmin, xmax, ymin, ymax;
bool isIn(int x, int y)
{
return x >= xmin && x <= xmax && y >= ymin && y <= ymax;
}
} slide[N];//slide[i]:字母编号为i的幻灯片
bool edge[N][N];//edge[i][j]:字母编号为i的幻灯片是否压着数字j
int n, deg[N], rec[N];//rec[i]:字母编号为i的幻灯片对应的数字
int find(int u)//对于入度只有1的数字顶点u，寻找与其对应的唯一字母顶点
{
for(int k = 0; k < n; ++k)
if(edge[k][u])//从字母k到数字u有边
return k;
}
bool topoSort()//返回是否成功完成类拓扑排序（删除数字结点数量是否为n）
{
int num = 0;//成功删除的数字结点数量
queue<int> que;
for(int i = 1; i <= n; ++i)//开始进行类拓扑排序，删除入度为1的数字顶点
if(deg[i] == 1)
que.push(i);
while(que.empty() == false)
{
int u = que.front(), k = find(u);//字母k指向数字u
que.pop();
rec[k] = u;//字母k与数字u对应
num++;
for(int i = 1; i <= n; ++i) if(edge[k][i])//删除从字母k到数字i的边
{
edge[k][i] = false;
if(--deg[i] == 1)//如果数字i入度为1，则入队
que.push(i);
}
}
return num == n;
}
int main()
{
int x, y;
cin >> n;
for(int i = 0; i < n; ++i)
cin >> slide[i].xmin >> slide[i].xmax >> slide[i].ymin >> slide[i].ymax;
for(int i = 1; i <= n; ++i)
{
cin >> x >> y;
for(int j = 0; j < n; ++j) if(slide[j].isIn(x, y))//如果x,y在幻灯片字母编号j的范围内
{
edge[j][i] = true;//幻灯片j压着数字i
deg[i]++;//数字编号i的入度增加
}
}
bool res = topoSort();
if(res)//配对成功
{
for(int i = 0; i < n; ++i)
cout << char('A'+i) << ' ' << rec[i] << endl;
}
else
cout << "None";
return 0;
}
上一题
下一题