Problem UVA11134-Fabled Rooks（贪心）

Problem UVA11134-Fabled Rooks

Accept: 716  Submit: 6134
Time Limit: 3000mSec

Problem Description

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 (xli,yli) and its rightlower corner (xri,yri), where 1 ≤ i ≤ n, 1 ≤ xli ≤ xri ≤ n, 1 ≤ yli ≤ yri ≤ n.

• No two rooks can attack each other, that is no two rooks can occupy the same column or the same row.

Input

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 xli, yli, xri, and yri. The input file is terminated with the integer ‘0’ on a line by itself.

 Output

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

 

题解：有了lrj前面几道关于区间的例题，这个题的贪心还是很好想的，首先因为行列独立，因此可以转化为两个问题分析，在区间1~n之间选n个互不相同的数，使得第i个数在区间[ai,bi].区间排序时按右端点递增排，右端点相同时按左端点从大到小排。每次选取区间最左边能选的点。当有一个区间不能选时就是IMPOSSIBLE.我粗略地证明一下：假设在当前区间不选可选的最左边的点，必定选取了一个更靠右的点，最左边的点肯定也是要填的，之后填这个格子的区间如果是左端点小于等于当前区间的区间，那么交换填的方式不影响可解性，如果左端点大于当前区间左端点，那么当前区间尽量向左填所得到的解不会比当前解差。有不对的地方，欢迎大家指教。

 

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn =  + ;

 int n;

 struct Interval {
     pair<int, int> interval;
     int pos;
 }hor[maxn], ver[maxn];

 bool cmp(const Interval &a, const Interval &b) {
     if (a.interval.second == b.interval.second) return a.interval.first > b.interval.first;
     else return a.interval.second < b.interval.second;
 }

 bool hvis[maxn], vvis[maxn];
 int vans[maxn], hans[maxn];

 int main()
 {
     //freopen("input.txt", "r", stdin);
     while (~scanf("%d", &n) && n) {
         memset(hvis, false, sizeof(hvis));
         memset(vvis, false, sizeof(vvis));
         int xl, yl, xr, yr;
         for (int i = ; i <= n; i++) {
             scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
             ver[i].interval = make_pair(xl, xr);
             ver[i].pos = i;
             hor[i].interval = make_pair(yl, yr);
             hor[i].pos = i;
         }

         sort(ver + , ver +  + n, cmp);
         sort(hor + , hor +  + n, cmp);

         bool ok = true;

         for (int i = ; i <= n; i++) {
             int l = ver[i].interval.first, r = ver[i].interval.second;
             int p = ver[i].pos;
             int j;
             for (j = l; j <= r; j++) {
                 if (!vvis[j]) {
                     vvis[j] = true;
                     vans[p] = j;
                     break;
                 }
             }
             if (j == r + ) { ok = false; break; }
         }

         if (!ok) {
             printf("IMPOSSIBLE\n");
             continue;
         }

         for (int i = ; i <= n; i++) {
             int l = hor[i].interval.first, r = hor[i].interval.second;
             int p = hor[i].pos;
             int j;
             for (j = l; j <= r; j++) {
                 if (!hvis[j]) {
                     hvis[j] = true;
                     hans[p] = j;
                     break;
                 }
             }
             if (j == r + ) { ok = false; break; }
         }

         if (!ok) {
             printf("IMPOSSIBLE\n");
             continue;
         }

         for (int i = ; i <= n; i++) {
             printf("%d %d\n", vans[i], hans[i]);
         }
     }
     return ;
 }

 

 Sample Output