UVA

题目：点击打开题目链接

思路：为了满足所有的车不能相互攻击，就要保证所有的车不同行不同列，于是可以发现，行与列是无关的，因此题目可以拆解为两个一维问题，即在区间[1-n]之间选择n个不同的整数，使得第i个整数在区间[x, y]内，此问题可以通过贪心法解决，但需要注意选择合适的贪心策略。我的贪心方法是：以后约束点为重点考察对象对点进行排序，然后遍历给每一个点选择最小的合适的下标，若找不到合适的下标，说明无解。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 5000 + 5;

struct point{
    int st, ed, id;
}x[maxn], y[maxn];

int n, cx[maxn], cy[maxn];

bool cmp(const point& temp1, const point& temp2) {
    return temp1.ed == temp2.ed ? temp1.st < temp2.st : temp1.ed < temp2.ed;
}

bool judge(int *arr, point *Point) {
    sort(Point, Point + n, cmp);
    int temp[maxn] = {0};

    for(int i = 0; i < n; i++) {
        bool ok = false;
        for(int j = Point[i].st; j <= Point[i].ed; j++) {
            if(!temp[j]) {
                ok = true;
                temp[j] = 1;
                arr[Point[i].id] = j;
                break;
            }
        }
        if(!ok) return false;
    }
    return true;
}

int main()
{
    while(cin >> n && n) {
        for(int i = 0; i < n; i++){
            cin >> x[i].st >> y[i].st >> x[i].ed >> y[i].ed;
            x[i].id = i;
            y[i].id = i;
        }
        memset(cx, 0, sizeof(cx));
        memset(cy, 0, sizeof(cy));
        if(judge(cx, x) && judge(cy, y)) {
            for(int i = 0; i < n; i++)
                cout << cx[i] << ' ' << cy[i] << endl;
        }
        else
            cout << "IMPOSSIBLE" << endl;

    }
    return 0;
}