/ ITcode / 讨论 / 游戏 /

一个类似导弹拦截的

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
int h;
int r;
}a[5005];
int n;
int pr[5005],head;
int flag,p,mn;
bool cmp (node x,node y)
{
if (x.h!=y.h) return x.h>y.h;
else return x.r>y.r;
}
int main()
{
//freopen("dg.in","r",stdin);
//freopen("dg.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&a[i].r,&a[i].h);
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
flag=1;
p=0;
mn=0x7ffffff;
for(int j=1;j<=head;j++)
{
if(pr[j]>=a[i].r)
{
flag=0;
if(mn>pr[j]-a[i].r)
{
mn=pr[j]-a[i].r;
p=j;
}
}
}
if(flag) pr[++head]=a[i].r;
else pr[p]=a[i].r;
}
printf("%d\n",head);
return 0;
}

2 条评论

  • 1