題目大意： 在一個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; }
