hdu 4268 multiset+贪心

Alice和Bob有n个长方形,有长度和宽度,一个矩形可以覆盖另一个矩形的条件的是,本身长度大于等于另一个矩形,且宽度大于等于另一个矩形,矩形不可旋转,问你Alice最多能覆盖Bob的几个矩形?

 /*
HDU 4268
贪心+STL
*/ #include<stdio.h>
#include<math.h>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int MAXN=;
struct Node
{
int h,w;
int flag;
}node[MAXN];
bool cmp(Node a,Node b)
{
if(a.h!=b.h)return a.h<b.h;
else if(a.w!=b.w)return a.w<b.w;
else return a.flag>b.flag;
}
multiset<int>mt;
multiset<int>::iterator it;
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int T;
int n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&node[i].h,&node[i].w);
node[i].flag=;
}
for(int i=n+;i<=*n;i++)
{
scanf("%d%d",&node[i].h,&node[i].w);
node[i].flag=;
}
sort(node+,node+*n+,cmp);
mt.clear();
/*for(int i=1;i<=2*n;i++)
{
printf("%d %d %d\n",node[i].h,node[i].w,node[i].flag);
}*/
int ans=;
for(int i=;i<=*n;i++) //1覆盖2
{
if(node[i].flag==)mt.insert(node[i].w);
else
{
if(!mt.empty())
{
it=mt.begin();
if(node[i].w>=(*it)) //multiset是升序排列的,每次begin是出来最小的值,这个值不一定最接近w,所以需要重新找
{
ans++;
it=mt.upper_bound(node[i].w);
it--;
mt.erase(it);
}
}
}
}
printf("%d\n",ans);
}
return ;
}
上一篇:javaweb学习总结(二十二)——基于Servlet+JSP+JavaBean开发模式的用户登录注册


下一篇:#LeetCode# Container With Most Water (todo)