首页 > 代码库 > UVa 11134 (区间上的贪心) Fabled Rooks
UVa 11134 (区间上的贪心) Fabled Rooks
这道题真是WA得我心力交瘁，好讨厌的感觉啊！
简直木有写题解的心情了
题意：
n×n的棋盘里，放置n个车，使得任意两车不同行且不同列，且第i个车必须放在给定的第i个矩形范围内。输出一种方案，即每个车的坐标，无解的话则输出“IMPOSSIBLE”
行和列是独立的，所以可以分开处理，将二维的转化成了一维区间上的取点问题：
有一个长度为n的区间，还有n个小区间，求一种方案，在每个小区间的范围取一个点，是的大区间上每个单位1的区间里都有点。
开始写的贪心是错误的：
按区间的左端点从小到大排序，然后右端点从小到大二级排序。
这里有个反例：
比如按这种方式排序后的区间是：[1, 3] [1, 3] [2, 2]
那么第一第二个点会放在前两个[1, 3]里面，而第三个点就放不下了。
但是显然这种情况是有合法方案的。
正确的贪心方式：
先对区间的右端点从小到大排序，然后左端点从大到小二级排序(满足区间短的先选)。
从区间的角度考虑：
然后对于每个区间，在它所覆盖的范围从左到右遍历，如果没有放点，就放进去。如果遍历完整个区间都没有点能放，就说明不存在合法方案。
从点考虑的话，我又WA掉了。。=_=||
将区间排序后，从第一个点开始，找到第一个能放进去的区间就放下。
下面是AC的代码君：
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 5000 + 10; 9 struct Node 10 { 11 int x1, x2, y1, y2; 12 int x, y; 13 int order; 14 }a[maxn]; 15 int n; 16 bool vis[maxn]; 17 18 bool cmp1(Node a, Node b) 19 { 20 return a.x2 < b.x2 || (a.x2 == b.x2 && a.x1 > b.x1); 21 } 22 23 bool cmp2(Node a, Node b) 24 { 25 return a.y2 < b.y2 || (a.y2 == b.y2 && a.y1 > b.y1); 26 } 27 28 bool cmp3(Node a, Node b) 29 { 30 return a.order < b.order; 31 } 32 33 int main(void) 34 { 35 #ifdef LOCAL 36 freopen("11134in.txt", "r", stdin); 37 #endif 38 39 while(scanf("%d", &n) == 1 && n) 40 { 41 for(int i = 0; i < n; ++i) 42 { 43 scanf("%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2); 44 a[i].order = i; 45 } 46 47 memset(vis, false, sizeof(vis)); 48 flag = true; 49 sort(a, a + n, cmp1); 50 for(int i = 0; i < n; ++i) 51 { 52 for(j = a[i].x1; j <= a[i].x2; ++j) 53 { 54 if(!vis[j]) 55 { 56 vis[j] = true; 57 a[i].x = j; 58 break; 59 } 60 } 61 if(j > a[i].x2) 62 { 63 flag = false; 64 break; 65 } 66 } 67 68 if(flag) 69 { 70 memset(vis, false, sizeof(vis)); 71 sort(a, a + n, cmp2); 72 for(int i = 0; i < n; ++i) 73 { 74 for(j = a[i].y1; j <= a[i].y2; ++j) 75 { 76 if(!vis[j]) 77 { 78 vis[j] = true; 79 a[i].y = j; 80 break; 81 } 82 if(j > a[i].y2) 83 { 84 flag = false; 85 break; 86 } 87 } 88 } 89 } 90 91 if(flag) 92 { 93 sort(a, a + n, cmp3); 94 for(int i = 0; i < n; ++i) printf("%d %d\n", a[i].x, a[i].y); 95 } 96 else 97 puts("IMPOSSIBLE"); 98 } 99 100 return 0;101 }
UVa 11134 (区间上的贪心) Fabled Rooks
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。