`
阿尔萨斯
  • 浏览: 4109632 次
社区版块
存档分类
最新评论

ZOJ 3041 City Selection(二维比较,排序分析)

 
阅读更多

ZOJ 3041 City Selection(二维比较,排序分析)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3041

题意:

现在有m个工厂和n个可建城市的地点,如果有一个工厂在一个地点的左上角,那么该地点就不可以建城市.现在要你输出所有可以建城市的点.

分析:

对于这种需要2维属性确立相对大小关系的,我们可以通过排序先确定一个维度属性的相对大小.

如果有工厂x坐标<=城市x坐标且y坐标>=城市y坐标,那么该城市点不可行.

首先我们通过排序按x从小到大,(如果x相等,y从小到大,如果xy都相等,就把工厂排在城市前面)的顺序排序.

现在我们确定了x坐标一定是从小到大排序的,所以如果我们当前考虑第i个点(该点是城市)是否可行时?我们只要从0到i-1这些点中找出是否有一个工厂的y坐标大于等于它的y坐标就行(因为这前面工厂的x坐标肯定<=该地点的x坐标).

所以程序中我们用y来记录我们当前所遇到过的所有工厂中y坐标的最大值.如果这个最大值依然小于当前城市点的y坐标,那么就不可能有妨碍该城市的工厂存在了.(自己想想是不是)

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define INF 2e10
const int maxn=200000*2+10;

struct Node
{
    int x,y;
    bool f;//true时表工厂
    bool operator<(const Node& rhs)const
    {
        return x<rhs.x ||(x==rhs.x && y<rhs.y)||(x==rhs.x && y==rhs.y && f);
    }
}nodes[maxn];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        for(int i=0;i<n;++i)
        {
            scanf("%d%d",&nodes[i].x,&nodes[i].y);
            nodes[i].f=false;
        }
        for(int i=n;i<n+m;++i)
        {
            scanf("%d%d",&nodes[i].x,&nodes[i].y);
            nodes[i].f=true;
        }
        sort(nodes,nodes+n+m);

        int ans=0;//最终能建city的地方数目
        int num[maxn];
        int y=-INF;//之前所有工厂中,y的最大值
        for(int i=0;i<n+m;++i)
        {
            if(nodes[i].f==true)//工厂
                y=max(y,nodes[i].y);
            else                //城市
            {
                if(y<nodes[i].y)//可建城市
                    num[ans++]=i;
            }
        }
        printf("%d\n",ans);
        for(int i=0;i<ans;++i)
            printf("%d %d\n",nodes[num[i]].x,nodes[num[i]].y);
    }
    return 0;
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics