一、题意

要求在n*n的棋盘上放n个车（n<=5000），使得任意两个车不相互攻击，且第i个车在一个给定的矩形里。
输入n，然后是n个车对应的矩形范围(xl, yl)，(xr,yr)，分别表示矩形的左上角和右下角。
若无解输出IMPOSSIBLE，有解则依次输出每个车的坐标。
多解时输出任意解即可。

二、解析

紫薯的提示：该问题行列是无关的，因此可以把原题分解为两个一维的问题。
一维的问题：将n个车放到1...n的位置上，每个车限定了一个区间范围。
这样就又变成了一个区间类的贪心问题。

容易想到，区间范围右端点越小的车我们应该尽早处理，不然它很快就会没有位置摆放了。因此我们把区间按照右端点从小到大排序（右端点相同则长的放前面）。每次摆放时，把车放在这个区间的最左端总是不会错的（因为这样能给后面的车留下更多的空间），因此我们只要依次放车，若出现有一个车找不到位置放，则说明无解。

三、代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 5000 + 5;
struct node {
    int l, r, idx;
    node(int l, int r, int idx) : l(l), r(r), idx(idx) {}
    bool operator < (const node& rhs) const {
        return r < rhs.r || r == rhs.r && l < rhs.l;
    }
};
vector<node> vec_x, vec_y;
int n, X[maxn], Y[maxn], vis[maxn];

bool solve(vector<node>& vec, int* ans) {
    fill(vis, vis + n + 1, 0);
    sort(vec.begin(), vec.end());
    for(const auto& p : vec) {
        int j = p.l;
        while(j <= p.r && vis[j]) j ++;
        if(j == p.r + 1) return 0;
        ans[p.idx] = j, vis[j] = 1;
    }
    return 1;
}

int main() {
    while(cin >> n && n) {
        vec_x.clear(), vec_y.clear();
        for(int i = 1, xl, yl, xr, yr; i <= n; i ++) {
            cin >> xl >> yl >> xr >> yr;
            vec_x.push_back(node(xl, xr, i));
            vec_y.push_back(node(yl, yr, i));
        }
        if(!solve(vec_x, X) || !solve(vec_y, Y)) cout << "IMPOSSIBLE" << endl;
        else for(int i = 1; i <= n; i ++) cout << X[i] << " " << Y[i] << endl;
    }
}

四、归纳

  • 区间限制问题：按区间的右端点排序，总是先处理快到“ddl”的区间。ps：结合实际生活来看，这的确是显然的。