uva 11134 Fabled Rooks

题目大意：
在一个n*n的棋盘上放置n个车，使得它们之间都不能互相攻击（任意两个车都不能同行或同列），并且，对于第i个车，限制它只能放在一个矩形区域内，(xli, yli)，这个矩形的左上角顶点坐标是(xli, yli)，右下角顶点坐标是 (xri, yri)， 1 ≤ i ≤ n, 1 ≤ xli ≤ xri ≤ n, 1 ≤ yli ≤ yri ≤ n.
 
思路：
这题其实可以把每个车的区域的x轴范围和y轴范围独立的看待，每个车在x轴上的区域为 【xl1, xr1】,【xl2, xr2】, 【xl3, xr3】...在y轴上的区域为【yl1, yr1】,【yl2, yr2】,【yl3, yr3】...
如果在x轴或y轴上的每一个区域上都放置一个棋子，并且不冲突，就满足条件。
判断方法用优先队列来维护，每次从所有区间【l, r】中选择 l 最小，并且r最小的区间来放置，还要维护一个当前已经放置到了第几个（maxx）, 如果有l<maxx，那么修改这个结点，把它的l改成maxx再放入队列中。
 
[cpp] 
/* 
     uva 11134 Fabled Rooks 
     贪心，优先队列 
*/  
#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<queue>  
using namespace std;  
  
const int maxn = 5010;  
int n;  
  
struct Node{  
    int l, r, id;  
    friend bool operator<(const Node& a, const Node&b){  
        if(a.l != b.l) return a.l > b.l;  
        return a.r > b.r;  
    }  
}arr1[maxn], arr2[maxn];  
int ans[maxn][2];  
  
bool check(Node* arr, int pos){  
    priority_queue<Node>Q;  
    for(int i=0; i<n; ++i) Q.push(arr[i]);  
    int maxx=0;  
    while(!Q.empty()){  
        Node tmp = Q.top();  
        Q.pop();  
        if(tmp.r < maxx) return false;  
        if(tmp.l < maxx){  
            tmp.l=maxx;  
            Q.push(tmp);  
            continue;  
        }  
        int cur = max(maxx, tmp.l);  
        ans[tmp.id][pos] = cur;  
        maxx = cur+1;  
    }  
    return true;  
}  
  
int main(){  
    int i,j;  
    while(~scanf("%d", &n) && n){  
        for(i=0; i<n; ++i){  
            scanf("%d%d%d%d",&arr1[i].l,&arr2[i].l,&arr1[i].r,&arr2[i].r);  
            arr1[i].id = arr2[i].id = i;  
        }  
          
        if(check(arr1,0) && check(arr2,1)){  
            for(i=0; i<n; ++i)  
                printf("%d %d\n", ans[i][0], ans[i][1]);  
        }else{  
            puts("IMPOSSIBLE");  
        }  
    }  
    return 0;  
}

补充：软件开发 , C++ ,