这道题真是WA得我心力交瘁，好讨厌的感觉啊！
简直木有写题解的心情了
题意：
n×n的棋盘里，放置n个车，使得任意两车不同行且不同列，且第i个车必须放在给定的第i个矩形范围内。输出一种方案，即每个车的坐标，无解的话则输出“IMPOSSIBLE”
行和列是独立的，所以可以分开处理，将二维的转化成了一维区间上的取点问题：
有一个长度为n的区间，还有n个小区间，求一种方案，在每个小区间的范围取一个点，是的大区间上每个单位1的区间里都有点。
开始写的贪心是错误的：
按区间的左端点从小到大排序，然后右端点从小到大二级排序。
这里有个反例：
比如按这种方式排序后的区间是：[1, 3] [1, 3] [2, 2]
那么第一第二个点会放在前两个[1, 3]里面，而第三个点就放不下了。
但是显然这种情况是有合法方案的。
正确的贪心方式：
先对区间的右端点从小到大排序，然后左端点从大到小二级排序(满足区间短的先选)。
从区间的角度考虑：
然后对于每个区间，在它所覆盖的范围从左到右遍历，如果没有放点，就放进去。如果遍历完整个区间都没有点能放，就说明不存在合法方案。
从点考虑的话，我又WA掉了。。=_=||
将区间排序后，从第一个点开始，找到第一个能放进去的区间就放下。
下面是AC的代码君：
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
struct Node
{
int x1, x2, y1, y2;
int x, y;
int order;
}a[maxn];
int n;
bool vis[maxn]; bool cmp1(Node a, Node b)
{
return a.x2 < b.x2 || (a.x2 == b.x2 && a.x1 > b.x1);
} bool cmp2(Node a, Node b)
{
return a.y2 < b.y2 || (a.y2 == b.y2 && a.y1 > b.y1);
} bool cmp3(Node a, Node b)
{
return a.order < b.order;
} int main(void)
{
#ifdef LOCAL
freopen("11134in.txt", "r", stdin);
#endif while(scanf("%d", &n) == && n)
{
for(int i = ; i < n; ++i)
{
scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
a[i].order = i;
} memset(vis, false, sizeof(vis));
flag = true;
sort(a, a + n, cmp1);
for(int i = ; i < n; ++i)
{
for(j = a[i].x1; j <= a[i].x2; ++j)
{
if(!vis[j])
{
vis[j] = true;
a[i].x = j;
break;
}
}
if(j > a[i].x2)
{
flag = false;
break;
}
} if(flag)
{
memset(vis, false, sizeof(vis));
sort(a, a + n, cmp2);
for(int i = ; i < n; ++i)
{
for(j = a[i].y1; j <= a[i].y2; ++j)
{
if(!vis[j])
{
vis[j] = true;
a[i].y = j;
break;
}
if(j > a[i].y2)
{
flag = false;
break;
}
}
}
} if(flag)
{
sort(a, a + n, cmp3);
for(int i = ; i < n; ++i) printf("%d %d\n", a[i].x, a[i].y);
}
else
puts("IMPOSSIBLE");
} return ;
}
代码君