题意：
给你n*n的棋盘，，让放置n个车 使他们之间并不能相互攻击
附加条件是 给定n个车的放置区间 用左上角和右下角的坐标来表示
解题思路：
首先明确 横向的约束和纵向的约束其实并不互相影响 所以可以对横向和纵向单独求解 把问题变成两个一维的区间选点问题来求解
另外 在取点的时候 有贪心的思路在里面 对于n个区间 应该先选择区间中r最小的区间进行放置可放置的点可以简单认为这是因为r越小的区间 其选择的灵活性就越低。
我刚开始的时候 是采取了先放置区间长度小的 在放置l小的区间 不正确。
code：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 5005;int n;struct node{int l,r;int len;int id;int pos;bool operator < (const node nt)const {//if(len != nt.len) return len < nt.len;if(r != nt.r) return r < nt.r;else return l < nt.l;}}qujian1[maxn],qujian2[maxn];bool cmp1(node n1, node n2){return n1.id < n2.id;}void init(){for(int i = 0; i < n; i++){scanf("%d%d%d%d",&qujian1[i].l,&qujian2[i].l,&qujian1[i].r,&qujian2[i].r);qujian1[i].id = i;qujian2[i].id = i;}for(int i = 0; i < n; i++){qujian1[i].len = qujian1[i].r – qujian1[i].l + 1;qujian2[i].len = qujian2[i].r – qujian2[i].l + 1;}// for(int i = 0; i < n; i++){//printf("========== %d %d\n",qujian1[i].l,qujian1[i].r);// }}int vis[maxn];int ans1[maxn],ans2[maxn];bool solve(){sort(qujian1,qujian1+n);// for(int i = 0; i < n; i++){//printf("========== %d %d\n",qujian1[i].l,qujian1[i].r);// }memset(vis, 0, sizeof(vis));for(int i = 0; i < n; i++){int x = qujian1[i].l;int y = qujian1[i].r;bool ok = false;for(int j = x; j <= y; j++){if(!vis[j]){vis[j] = 1;//ans1[cnt++] = j;qujian1[i].pos = j;//printf("==========%d\n",j);ok = true;break;}}if(!ok) return false;}sort(qujian2,qujian2+n);memset(vis, 0, sizeof(vis));for(int i = 0; i < n; i++){int x = qujian2[i].l;int y = qujian2[i].r;bool ok = false;for(int j = x; j <= y; j++){if(!vis[j]){vis[j] = 1;//ans2[cnt++] = j;qujian2[i].pos = j;ok = true;break;}}if(!ok) return false;}sort(qujian1,qujian1+n,cmp1);sort(qujian2,qujian2+n,cmp1);for(int i = 0; i < n; i++){printf("%d %d\n",qujian1[i].pos,qujian2[i].pos);}return true;}int main(){while(scanf("%d",&n) != EOF){if(n == 0) break;init();bool flag = solve();if(!flag){printf("IMPOSSIBLE\n");}}return 0;}
不要因为生活琐事而烦恼,不要因为儿女情长而忧愁,
