程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11134 Fabled Rooks 優先隊列

UVA 11134 Fabled Rooks 優先隊列

編輯：C++入門知識

UVA 11134 Fabled Rooks 優先隊列

題意：有一個NxN的棋盤，你需要在上面放N個車，它們互相之間不能攻擊到，並且每個車只能放在指定的矩形范圍裡面。

思路：首先車之間不能互相攻擊，那麼每行每列有且僅有一個車，我們把每個車用坐標(x,y)表示出來，那麼最後要求的其實就是任意兩個車的x坐標要不一樣，任意兩個車的y坐標不一樣。然後每個車的x和y有自己的范圍.....！！！x和y是相互獨立的，不會相互影響！！所以我們只需要先求出各自的橫坐標，然後再求出各自的縱坐標就行了，不是嗎？這時候，問題就變得相當簡單了。我們的題目變成了在一條X軸上，有n條線段，每條線段你必須取一個點，而且每個線段取的點要互不相同。這個我們不是做過嗎？直接用優先隊列貪心就行了。

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rrep(i,b,a) for(int i=(b);i>=(int)(a);--i)
#define clr(a,x) memset(a,x,sizeof(a))
#define mp make_pair
#define eps 1e-10
#define LL long long
#define zero(x) (-eps < (x) && (x) < eps)
const int maxn = 5000 + 5;
int lx[maxn],rx[maxn],ly[maxn],ry[maxn];
int X[maxn],Y[maxn];
vector v[maxn];
int n;
bool Try(int *l, int * r,int * ret){
    rep(i,0,n) v[i].clear();
    rep(i,0,n) v[l[i]].push_back(i);
    priority_queue > q;
    rep(i,0,n){
        rep(j, 0, v[i].size()){
        int x = v[i][j];
        q.push(mp(-r[x],x) );
        }
        if(q.empty() || -q.top().first < i)  return false;
        int c = q.top().second; q.pop();
        ret[c]=i;
    }
    return true;
}
bool solve(){
    if(!Try(lx,rx,X) || !Try(ly,ry,Y)) return false;
    rep(i,0,n) printf("%d %d\n",X[i]+1, Y[i]+1);
    return true;
}
int main()
{
    while(scanf("%d",&n),n){

        rep(i,0,n){
            scanf("%d%d%d%d",lx+i,ly+i,rx+i,ry+i);
            --lx[i];--ly[i];--rx[i];--ry[i];
        }
        if(!solve()) puts("IMPOSSIBLE");
    }
    return 0;
}