程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA 11134 Fabled Rooks 優先隊列

UVA 11134 Fabled Rooks 優先隊列

編輯:關於C++

題意:有一個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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved