比赛 |
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;
}