UVA 11134 FabledRooks 传说中的车 （问题分解）

摘要：贪心，问题分解。

因为行列无关，所以这个二维问题可以分解成两个一维问题。

优先队列实现：类似区间点覆盖的问题，先按照左端点排序，相同然后在按右端点排序（灵活性小的优先选）。最优的选法，当然是要使选的这个点经过的区间越少越好，那么就选最左边的点，因为选右边可能多经过区间，一定不比选最左边的更优。选完之后，就要把选过的点last忽略，并且把包含这个点的区间做修改，这个修改是动态的，可用优先队列

71ms

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5003;
struct seg
{
    int l,r,id;
    seg(int L,int R) { l = L; r = R; }
    seg(){}
    bool operator < (const seg& rhs) const {
        return l > rhs.l || ( l == rhs.l && r > rhs.r);
    }
};

seg dim[2][maxn];
int rooks[maxn][2];

priority_queue<seg> q;

bool solve(int n,int d)
{
    for(int i = 0; i < n; i++){
       q.push(dim[d][i]);
    }
    int last = 0;
    int id = 0;
    while(q.size()){
        seg cur = q.top(); q.pop();
        if(cur.l>cur.r) return false;
        if(cur.l<=last) {
            cur.l = last + 1; q.push(cur);
        }else {
            last = cur.l;
            rooks[cur.id][d] = cur.l;
        }
    }
    return true;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    seg *R = dim[0], *C = dim[1];
    for(int i = 0; i < maxn; i++) dim[0][i].id = dim[1][i].id = i;
    while(~scanf("%d",&n)&&n){
        for(int i = 0; i < n; i++){
            scanf("%d%d%d%d",&R[i].l,&C[i].l,&R[i].r,&C[i].r);
        }
        if(solve(n,0)&&solve(n,1)){
             for(int i = 0; i < n; i++){
            printf("%d %d
",rooks[i][0],rooks[i][1]);
            }
        }else puts("IMPOSSIBLE");

    }
    return 0;
}

另外一种贪心，直接按照右端点排序，优先处理右端点最小的区间，因为它的灵活性最小。从左往右边选点，使当前点尽量避免经过没有选点的区间。

这样做的效率要更高

11ms

#include<bits/stdc++.h>
using namespace std;

const int maxn = 5003;
struct seg
{
    int l,r,id;
    bool operator < (const seg& rhs) const {
        return r < rhs.r ;
    }
};

seg dim[2][maxn];
int rooks[maxn][2];


bool solve(int n,int d)
{
    int last = -1;
    seg *Dim = dim[d];
    bool vis[n+1];
    memset(vis,0,sizeof(vis));
    sort(Dim,Dim+n);
    for(int i = 0; i < n; i++){
        int j;
        for(j = Dim[i].l; j <= Dim[i].r; j++) if(!vis[j]) {
                rooks[Dim[i].id][d] = j; vis[j] = true; break;
        }
        if(j>Dim[i].r) return false;
    }
    return true;
}

int main()
{
    int n;
    seg *R = dim[0], *C = dim[1];
    while(~scanf("%d",&n)&&n){
        for(int i = 0; i < n; i++){
            scanf("%d%d%d%d",&R[i].l,&C[i].l,&R[i].r,&C[i].r);
            R[i].id = C[i].id = i;
        }
        if(solve(n,0)&&solve(n,1)){
             for(int i = 0; i < n; i++){
            printf("%d %d
",rooks[i][0],rooks[i][1]);
            }
        }else puts("IMPOSSIBLE");

    }
    return 0;
}