UVA 11134 Fabled Rooks 优先队列 - c++编程基础

TOP

UVA 11134 Fabled Rooks 优先队列

2015-11-21 00:59:03 来源: 作者: 【大中小】浏览:1次

题意：有一个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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 1505 City Game-dp-（最大子..	下一篇：C++ 成员函数返回引用，三种获取..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: