首页 > 其他 > 详细

uva 11134

时间:2017-05-11 10:58:28      阅读:295      评论:0      收藏:0      [点我收藏+]

给定区间求每个棋子的位置,横坐标和纵坐标分开,贪心找到各不相交的点,x,y组合就行了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=5000+10;
struct note
{
    int l,r;
    int id;
    bool operator < (const note &p) const
    {
        return (l>p.l)||(l==p.l&&r>p.r);
    }
}a[maxn],b[maxn];//横坐标是a,纵坐标是b
int aa[maxn][5];
int n;
int jude(note *c,int pos)
{
   priority_queue<note> qq;
   for(int i=0;i<n;i++)
        qq.push(c[i]);
   int ppos=0;//要呆的位置
   while(qq.size())
   {
       note cc=qq.top(); qq.pop();
       if(cc.r<ppos) return 0;
       if(cc.l<ppos)
       {
           cc.l=ppos;
           qq.push(cc);//更新区间,重新遍历
           continue;
       }
       aa[cc.id][pos]=cc.l;
       ppos=cc.l+1;
   }
   return 1;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d%d",&a[i].l,&b[i].l,&a[i].r,&b[i].r);
            a[i].id=i;
            b[i].id=i;
        }
        if(jude(a,0)&&jude(b,1))
        {
            for(int i=0;i<n;i++)
                printf("%d %d\n",aa[i][0],aa[i][1]);
        }
        else printf("IMPOSSIBLE\n");
    }
    return 0;
}

 

uva 11134

原文:http://www.cnblogs.com/Wangwanxiang/p/6839773.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!