比赛 20140421 评测结果 WWWWWWAAWW
题目名称 导弹拦截 最终得分 20
用户昵称 Dijkstra 运行时间 0.011 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2014-04-21 10:02:04
显示代码纯文本
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("bomba.in");
ofstream fout("bomba.out");
int N,ans1=0,ans2=0;
bool u[1001]={0};
struct point
{
	int x,y,z,n;
}p[1001];
bool JUD()
{
	int i;
	for(i=1;i<=N;i++) if(u[i]==0) return true;
	return false;
}
bool cmp(point a,point b)
{
	if(a.x<b.x&&a.y<b.y&&a.z<b.z)return 1;
	if(a.x==b.x&&a.y<b.y&&a.z<b.z)return 1;
	if(a.x==b.x&&a.y==b.y&&a.z<b.z)return 1;
	return 0;
}
bool cmp2(point a,point b)
{
	return a.x<b.x&&a.y<b.y&&a.z<b.z;
}
int main()
{
    fin>>N;
	int i;
	for(i=1;i<=N;i++){fin>>p[i].x>>p[i].y>>p[i].z;p[i].n=i;}
	sort(p+1,p+N+1,cmp);
	p[0]=(point){-1,-1,-1,0};
    while(JUD())
	{
		int m=0,s=0;
		i=1;
		while(i<=N)
		{
			if(u[i]){i++;continue;}
			if(p[i].n>p[m].n&&cmp2(p[m],p[i]))
			{
				u[i]=1;
				m=i;
				s++;
			}
			i++;
		}
		ans1=max(ans1,s);
		ans2++;
	}
	fout<<ans1<<endl<<ans2<<endl;
	return 0;
}