题解:Fabled Rooks

算法

地址：https://vjudge.net/problem/UVA-11134

Published

April 12, 2022

题解 : Fabled Rooks

1.题意

地址：https://vjudge.net/problem/UVA-11134

We would like to place n rooks, 1 ≤ n ≤ 5000, on a n × n board subject to the following restrictions • The i-th rook can only be placed within the rectangle given by its left-upper corner (xl , yl) and its rightlower corner (xr , yr), where 1 ≤ i ≤ n, 1 ≤ xl ≤ xr ≤ n , 1 ≤ yl ≤ yr ≤ n. • No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.

大概意思是，把n个棋子放在一个n*n的棋盘里，求任意一种方案。每个棋子有一个题目给出的位置区间xl,yl,xr,yr

2.思路

很显然，对于每一个棋子行和列的决策互不干扰，对于行或列，只要没有任意两个或以上棋子在同一行/列，方案合法，所以我们可以对于每一个棋子分别计算行和列的位置。

目前目前看到了三种方法：

假设我们现在在处理每个棋子的行位置

1.以每个棋子的限制区间的右端点从小到大排序，显然右端点越小越应该先给它分位置。然后放在这个棋子限制区间地最靠左的空位上。时间复杂度是o(n^2)，索性这个题n最大只有5000，我开始时想到使用类似 lowbit 函数的方法把每个位置的使用情况放在bitset里面这样查询某个棋子限制区间地最靠左的空位的时候就会变成o(1)，但是仔细想想这个过程仍然是o(n)的。
2.考虑把每个位置分配给每个区间，先把所有的限制区间按照右端点从小到大排序，然后从左到右遍历每个位置，将区间按顺序放进堆里，堆按照每个区间的左端点排序，一旦有区间的左端点<=当前位置，就把当前位置分配给该区间。对于这种方法的正确性其实和第一种方法差不多。在一定意义上可以算是对第一种方法的优化。时间复杂度o(nlogn)，十分优秀
3.网络流

当然还是有一些细节需要处理的，比如说把算的时候要记录每个点的序号，不然排序以后就乱了。最后输出答案以前记得按序号排回去

3.代码：

提供第一种方法的代码，因为懒

 #include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 const int MAXN = 1e5+7;
 template <typename _TP>
 inline void qread(_TP &X){
     char ch=0;int w;X=0;
     while(!isdigit(ch)){w=ch=='-';ch=getchar();}
     while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
     X=w?-X:X; 
 }
 int vis[MAXN];
 struct node{
     int num,l,r;
 }ax[MAXN],ay[MAXN];
 struct ansNode{
     int num,val;
 }ansx[MAXN],ansy[MAXN];
 inline bool cmpAns(const ansNode &a,const ansNode &b){
     return a.num<b.num;
 }
 inline bool cmp(const node &a,const node &b){
     return a.r<b.r;
 } 
 inline void INIT(){
     memset(vis,0,sizeof(vis));
 }
 void solve(const int n){
     INIT();
     int xl,yl,xr,yr;
     for(int i=1;i<=n;i++){
         qread(xl);qread(yl);qread(xr);qread(yr);
         ax[i]=(node){i,xl,xr};
         ay[i]=(node){i,yl,yr};
     }
     sort(ax+1,ax+n+1,cmp);
     for(int i=1;i<=n;i++){
         ansx[i].num=ax[i].num;
         int flag=0;
         for(int j=ax[i].l;j<=ax[i].r;j++){
             if(!vis[j]){
                 vis[j]=1;
                 ansx[i].val=j;
                 flag=1;
                 break;
             }
         }
         if(!flag){
             cout<<"IMPOSSIBLE\n";
             return ;
         }
     }
     sort(ay+1,ay+n+1,cmp);
     memset(vis,0,sizeof(vis));
     for(int i=1;i<=n;i++){
         ansy[i].num=ay[i].num;
         int flag=0;
         for(int j=ay[i].l;j<=ay[i].r;j++){
             if(!vis[j]){
                 vis[j]=1;
                 ansy[i].val=j;
                 flag=1;
                 break;
             }
         }
         if(!flag){
             cout<<"IMPOSSIBLE\n";
             return ;
         }
     }
     sort(ansx+1,ansx+n+1,cmpAns);
     sort(ansy+1,ansy+n+1,cmpAns);
     for(int i=1;i<=n;i++){
         cout<<ansx[i].val<<' '<<ansy[i].val<<'\n';
     }
 }
 int main(){
     int t;
     while(true){
         qread(t);
         if(!t)break;
         solve(t);
     }
     return 0;
 }