烦人的幻灯片 Sorting Slides

2023-11-22 12:41:10

Description

李教授将于今天下午作一次非常重要的演讲。不信的事他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用 \(n\) 张幻灯片（ \(n \le 26\)），这 \(n\) 张幻灯片按照演讲要使用的顺序已经用数字 \(1\) ~ \(n\)编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。

现在我们用大写字母 \(A\),\(B\),\(C\)……再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。

Input

文件的第一行只有一个整数 \(n\)，表示有 \(n\) 张幻灯片，接下来的 \(n\) 行每行包括4个整数 \(x_{min}\) , \(x_{max}\) , \(y_{min}\) , \(y_{max}\)（整数之间用空格分开）为幻灯片的坐标，这n张幻灯片按其在文件中出现的顺序从前到后依次编号为 \(A\),\(B\),\(C\)……，再接下来的 \(n\) 行依次为 \(n\) 个数字编号的坐标 \(x\) , \(y\)，显然在幻灯片之外是不会有数字的。

Output

若是对应可以实现，输出文件应该包括 \(n\) 行，每一行为一个字母和一个数字，中间以一个空格隔开，并且每行以字母的升序排列，注意输出的字母要大写并且定格；反之，若是对应无法实现，在文件的第一行顶格输出None即可。首行末无多余的空格。

Sample Input

Sample Output

A 4
B 1
C 2
D 3

可能会有多个数字在同一个字母的范围内，但一个字母只能对应数字。考虑用拓扑排序。

思路

找到入度为 \(1\) 的字母，那么可以确定该字母所对应的数字；
将与该数字有关的边全部删除；
重复上述步骤；
如果遍历到的字母数小于n，那么就是无解的情况，直接输出None。

为了方便删除边，可以用邻接矩阵存图。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn=105;
struct ppt
{
    int x1,x2,y1,y2;
} co[maxn];
struct point
{
    int x,y;
} pos[maxn];
int n,sum;
int ind[maxn],link[maxn];
bool G[maxn][maxn];
void topo()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(ind[i]==1) q.push(i);   //找到入度为 1 的字母
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        sum++;       //统计遍历到的字母数 
        int temp;
        for(int i=1;i<=n;i++)
        {
            if(G[i][u])
            {
                temp = i;     //确定该字母所对应的数字 
                break;
            }
        }
        link[u] = temp;
        for(int i=1;i<=n;i++)
        {
            if(G[temp][i])     //将与该数字有关的边全部删除 
            {
                G[temp][i] = false;
                ind[i]--;
            }
            if(ind[i]==1) q.push(i);    //找到入度为 1 的字母
        }
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&co[i].x1,&co[i].x2,&co[i].y1,&co[i].y2); 
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&pos[i].x,&pos[i].y); 
        for(int j=1;j<=n;j++)
        {
            if(pos[i].x>=co[j].x1&&pos[i].x<=co[j].x2&&pos[i].y>=co[j].y1&&pos[i].y<=co[j].y2)
            {
                G[i][j] = true;
                ind[j]++;
            }
        }
    }
    topo();
    if(sum<n) puts("None");
    else
    {
        for(int i=1;i<=n;i++)
        {
            printf("%c %d\n",'A'+i-1,link[i]);
        }
    }
    return 0;
}

码农公寓