第四十三题 UVA11134 传说中的车 Fabled Rooks

传说中的车 Fabled Rooks"/>

第四十三题 UVA11134 传说中的车 Fabled Rooks

输入格式

输出格式

题意翻译
在一个n*n（1<=n<=5000）的棋盘上放置n个车，每个车都只能在给定的一个矩形（xli,xri,yli,yri)里放置，使其n个车两两不在同一行和同一列，判断并给出解决方案。

感谢@zhbayl000 提供的翻译

输入输出样例
输入 #1复制
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
0
输出 #1复制
1 1
5 8
2 4
4 2
7 3
8 5
6 6
3 7
1 1
5 8
2 4
4 2
7 3
8 5
6 6
3 7

本题好像横坐标和纵坐标互不相干 于是可以分别处理
对于横坐标 选择其又端点尽量靠左的，以尽量减少对后面点的影响
纵坐标同理

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define Maxn 5002
using namespace std;
struct Node {int id,lx,ly,rx,ry;int ansx,ansy,usedx,usedy;
}rb[Maxn];
inline bool cmp_x(Node a,Node b){ return a.rx < b.rx; }
inline bool cmp_y(Node a,Node b){ return a.ry < b.ry; }
inline bool cmp_id(Node a,Node b) { return a.id < b.id; }int main(int argc,char* argv[]) {int n;while(scanf("%d",&n) == 1 && n) {for(int i=1; i<=n; i++) {rb[i].usedx = rb[i].usedy = 0;rb[i].id = i;scanf("%d %d %d %d",&rb[i].lx,&rb[i].ly,&rb[i].rx,&rb[i].ry);}sort(rb + 1,rb + n + 1,cmp_x); int can;for(int i=1; i<=n; i++) {can = 0;for(int j=1; j<=n; j++) {if(rb[j].usedx == 0 && rb[j].lx <= i) {if(rb[j].rx < i) break;rb[j].ansx = i; rb[j].usedx = 1; can = 1; break;}}if(!can) break;}if(!can) printf("IMPOSSIBLE\n");else {sort(rb + 1 ,rb + n + 1,cmp_y);for(int i=1; i<=n; i++) {can = 0;for(int j=1; j<=n; j++){if(rb[j].usedy == 0 && rb[j].ly <= i) {if(rb[j].ry < i) break;rb[j].ansy = i; rb[j].usedy = 1;can = 1; break;}}if(!can) break;}if(!can) printf("IMPOSSIBLE\n");else {sort(rb + 1,rb + n + 1,cmp_id);for(int i=1; i<=n; i++) printf("%d %d\n",rb[i].ansx,rb[i].ansy);}}}return 0;
}

刘老师的代码没有排序，而是每次O（N）扫描，也可，运行效率应该会低，但是他的代码是真的简洁 有必要粘贴一下

#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;// solve 1-D problem: find c so that a[i] <= c[i] <= b[i] (0 <= i < n)
bool solve(int *a, int *b, int *c, int n) {fill(c, c+n, -1);for(int col = 1; col <= n; col++) {// find a rook with smalleset b that is not yet assignedint rook = -1, minb = n+1;for(int i = 0; i < n; i++)if(c[i] < 0 && b[i] < minb && col >= a[i]) { rook = i; minb = b[i]; }if(rook < 0 || col > minb) return false;c[rook] = col;}return true;
}const int maxn = 5000 + 5;
int n, x1[maxn], y1[maxn], x2[maxn], y2[maxn], x[maxn], y[maxn];int main() {while(scanf("%d", &n) == 1 && n) {for (int i = 0; i < n; i++)scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);if(solve(x1, x2, x, n) && solve(y1, y2, y, n))for (int i = 0; i < n; i++) printf("%d %d\n", x[i], y[i]);elseprintf("IMPOSSIBLE\n");}return 0;
}