ZOJ 3041 City Selection(二维比较,排序分析)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3041
题意:
现在有m个工厂和n个可建城市的地点,如果有一个工厂在一个地点的左上角,那么该地点就不可以建城市.现在要你输出所有可以建城市的点.
分析:
对于这种需要2维属性确立相对大小关系的,我们可以通过排序先确定一个维度属性的相对大小.
如果有工厂x坐标<=城市x坐标且y坐标>=城市y坐标,那么该城市点不可行.
首先我们通过排序按x从小到大,(如果x相等,则y从小到大,如果x和y都相等,就把工厂排在城市前面)的顺序排序.
现在我们确定了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;
}
分享到:
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
Determine the Price For the manager of a theatre, setting the price of a ticket is a rather delicate matter. Suppose that a theatre has n () seats, and that if you give away the tickets for free, all ...
zoj4041正确题解源代码,以及运行程序
大学ACM竞赛,ZOJ 1733 运用递归(优化)的方法。ac的代码。
zoj 1002 C语言的为什么描述要这么多字啊。。
700道题的源代码啊,管用的.。。。。。。