题解_UVA_11134_Fabled Rooks_综合

题解_UVA_11134_Fabled Rooks

1.题意：

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 ( $x l, y l$ ) and its rightlower corner $(x r, y r)$ , 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.网络流

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

代码：

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

#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;
}