首页 > 代码库 > uva11134 - Fabled Rooks（问题分解，贪心法）
uva11134 - Fabled Rooks（问题分解，贪心法）
这道题非常好，不仅用到了把复杂问题分解为若干个熟悉的简单问题的方法，更是考察了对贪心法的理解和运用是否到位。
首先，如果直接在二维的棋盘上考虑怎么放不好弄，那么注意到x和y无关（因为两个车完全可以在同一条斜线上，这点和皇后问题不一样），那么就可以分别考虑两个一维的问题：这是一种区间选点问题，在每个区间里都只选一个点，最后这些点分别是1到n。这就联想到这样一个经典的贪心法解决的区间选点问题：数轴上有n个闭区间[ai,bi],选取尽量少的点，使得每个区间都至少含有一个点。这个问题的解决方法就是把所有区间按b从小到大排序（b相同时a从大到小排）。然后第一个区间选最右边的点（这个点影响到的区间最多，而且第一个区间肯定是要选的，那么既然怎么也是选，那我就选最好的那个。这就是贪心法的思维），后边的也按这种想法就行了（已经被前面的点影响到的区间就不用再选点了）。
本题的区间选点也可以用贪心的方法来做，但是以下两种生搬上面经典问题解法的方法是错误的：
一.把所有区间按左端排序，然后每次选能选的最左边的。
反例：[1,1],[1,3],[2,2];
二.由上面的例子看出：区间的长度也有影响，不能只看左端的顺序。那么如果先安排长度短的区间，如果区间长度相同再每次选最左边的行不行呢？
也是不行滴。。。反例：[1,1],[2,3],[3,4],[1,3].如果按这种思路选，那么最后一个位置就没有可选的了，结论是输出IMPOSSIBLE，但实际上很明显最后可以选好。
那么问题来了：为什么这两种思路不对？不就是按照那个经典问题的路子走的吗？
其实原因在于对贪心法的理解不到位，贪心法是每步选择局部最优解，然后一步一步向目标迈进。这个“目标”两字很关键，说明贪心法是目标导向的，每一步的方向一定是目标。那么我上面两种方法其实只是在模仿那个经典问题的模式，但是却没有时刻注意到这个问题最终目标是实现从1到n每一位都能放上满足条件的车，比如第二个反例最后一个格最后都无法放车了，就是因为前面没有按照对最终目标的影响效果去选择局部最优解，单纯的选最左边一个是毫无道理的，因为本题已经不是那个经典的选最少点的问题了。
正确的贪心法应该是这样：
从1到n一个格一个格的选车放，每步选择的最优区间是：该区间以前没选过，包含这个格，而且右端点是所有没选过的区间里最小的，那么我选择这个区间就最大程度的防止了以后的格子没得选（因为右端点选的是最小的）。
大致思路就是这样，在具体的代码实现中，我的做法是先按右端点排好序，然后按格选。看了github上的紫书答案，是不事先排序而每次都扫一遍然后找出最小的右端点，这种方式的时间复杂的稍高了一些，实际测试情况也是如此。
下面是我的代码：
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long int#define maxn 5000+5int n;bool can;struct node{ int id,lx,ly,rx,ry; int ansx,ansy,usedx,usedy;}rook[maxn];bool cmp_x(node a,node b){ return a.rx<b.rx;}bool cmp_y(node a,node b){ return a.ry<b.ry;}bool cmp_id(node a,node b){ return a.id<b.id;}int main(){ while(scanf("%d",&n)==1&&n) { for(int i=0;i<n;i++) { rook[i].usedx=rook[i].usedy=0; rook[i].id=i+1; scanf("%d%d%d%d",&rook[i].lx,&rook[i].ly,&rook[i].rx,&rook[i].ry); } sort(rook,rook+n,cmp_x); for(int i=1;i<=n;i++)//一格一格的看 { can=0; for(int j=0;j<n;j++) { if(rook[j].usedx==0&&rook[j].lx<=i) { if(rook[j].rx<i){break;} rook[j].usedx=1; rook[j].ansx=i; can=1; break; } } if(can==0) break; } if(can==0) printf("IMPOSSIBLE\n"); else { sort(rook,rook+n,cmp_y); for(int i=1;i<=n;i++) { can=0; for(int j=0;j<n;j++)//同样是一格一格的看 { if(rook[j].usedy==0&&rook[j].ly<=i) { if(rook[j].ry<i){break;} rook[j].usedy=1; rook[j].ansy=i; can=1; break; } } if(can==0) break; } if(can==0) printf("IMPOSSIBLE\n"); else { sort(rook,rook+n,cmp_id); for(int i=0;i<n;i++) { printf("%d %d\n",rook[i].ansx,rook[i].ansy); } } } } return 0;}
时间是0.079s
下面是github上的答案代码：
// UVa11134 Fabled Rooks// Rujia Liu#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 assigned int 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], yy1[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], &yy1[i], &x2[i], &y2[i]); if(solve(x1, x2, x, n) && solve(yy1, y2, y, n)) for (int i = 0; i < n; i++) printf("%d %d\n", x[i], y[i]); else printf("IMPOSSIBLE\n"); } return 0;}
时间是0.292s
uva11134 - Fabled Rooks（问题分解，贪心法）