Uva 11134 Fabled Rooks (問題分解 + 貪心放置)

Uva 11134 Fabled Rooks (問題分解 + 貪心放置)

題意：

給你n*n的棋盤，讓放置n個車 使他們之間並不能相互攻擊

附加條件是 給定n個車的放置區間 用左上角和右下角的坐標來表示

解題思路：

首先明確 橫向的約束和縱向的約束其實並不互相影響 所以可以對橫向和縱向單獨求解 把問題變成兩個一維的區間選點問題來求解

另外 在取點的時候 有貪心的思路在裡面 對於n個區間 應該先選擇區間中r最小的區間進行放置可放置的點 可以簡單認為這是因為r越小的區間 其選擇的靈活性就越低。

我剛開始的時候 是采取了先放置區間長度小的 在放置l小的區間 不正確。

code：

#include
#include
#include
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;
}