UVA 11134 - Fabled Rooks(贪心+优先队列)

本文主要是介绍UVA 11134 - Fabled Rooks(贪心+优先队列)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• The i-th rook can only be placed within the rectangle given by its left-upper corner (xl_i, yl_i) and its right-lower corner (xr_i, yr_i), where 1 ≤ i ≤ n, 1 ≤ xl_i ≤ xr_i ≤ n, 1 ≤ yl_i ≤ yr_i ≤ n.
• No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.

The input consists of several test cases. The first line of each of them contains one integer number, n, the side of the board. n lines follow giving the rectangles where the rooks can be placed as described above. The i-th line among them gives xl_i, yl_i, xr_i, and yr_i. The input file is terminated with the integer `0' on a line by itself.

Your task is to find such a placing of rooks that the above conditions are satisfied and then output n lines each giving the position of a rook in order in which their rectangles appeared in the input. If there are multiple solutions, any one will do. Output IMPOSSIBLE if there is no such placing of the rooks.

Sample input

8
1 1 2 2
5 7 8 8
2 2 5 5
2 2 5 5
6 3 8 6
6 3 8 5
6 3 8 8
3 6 7 8
8
1 1 2 2
5 7 8 8
2 2 5 5
2 2 5 5
6 3 8 6
6 3 8 5
6 3 8 8
3 6 7 8
0

Output for sample input

1 1
5 8
2 4
4 2
7 3
8 5
6 6
3 7
1 1
5 8
2 4
4 2
7 3
8 5
6 6
3 7

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;const int N = 5005;int n, ans1[N], ans2[N];
struct Car {int l, r, p, id;friend bool operator < (Car a, Car b) {return a.r > b.r;}
} c1[N], c2[N];bool cmp(Car a, Car b) {return a.l < b.l;
}bool cmpid(Car a, Car b) {return a.id < b.id;
}
void init() {for (int i = 1; i <= n; i ++) {scanf("%d%d%d%d", &c1[i].l, &c2[i].l, &c1[i].r, &c2[i].r);c1[i].id = c2[i].id = i;}sort(c1 + 1, c1 + 1 + n, cmp);sort(c2 + 1, c2 + 1 + n, cmp);
}bool judge(Car *c, int *ans) {priority_queue<Car> Q;int num = 1;for (int i = 1; i <= n; i ++) {while (c[num].l <= i  && c[num].r >= i && num <= n) {Q.push(c[num++]);}if (Q.empty()) return false;Car s = Q.top(); Q.pop();if (i > s.r) return false;ans[s.id] = i;}return true;
}void solve() {if (!judge(c1, ans1) || !judge(c2, ans2)) {printf("IMPOSSIBLE\n"); return;}for (int i = 1; i <= n; i ++)printf("%d %d\n", ans1[i], ans2[i]);
}int main() {while (~scanf("%d", &n) && n) {init();solve();}return 0;
}

这篇关于UVA 11134 - Fabled Rooks(贪心+优先队列)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！