hdu 4268 Alice and Bob(贪心+multiset)

题意:卡牌覆盖,每张卡牌有高(height)和宽(width)。求alice的卡牌最多可以覆盖多少bob的卡牌

思路:贪心方法就是找h可以覆盖的条件下找w最大的去覆盖。

#include<iostream>
#include<stdio.h>
#include<set>
#include<algorithm>
using namespace std; struct Node{
int h,w;
int flag;
}node[]; bool cmp(Node a,Node b){
if(a.h!=b.h)return a.h<b.h;//升序
if(a.w!=b.w)return a.w<b.w;//升序
return a.flag>b.flag;//降序
} multiset<int>mt;
multiset<int>::iterator it; int main(){
int t,n,i,ans;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=;i<=n;++i){
scanf("%d%d",&node[i].h,&node[i].w);
node[i].flag=;
}
for(i=n+;i<=*n;++i){
scanf("%d%d",&node[i].h,&node[i].w);
node[i].flag=;
}
sort(node+,node++*n,cmp);
mt.clear();
ans=;
for(i=;i<=*n;++i){
if(node[i].flag==)mt.insert(node[i].w);
else{
if(!mt.empty()){
it=mt.begin();
if(node[i].w>=(*it)){
++ans;
it=mt.upper_bound(node[i].w);//指向键值> key的第一个元素。
--it;//指向键值<= key的第一个元素。
mt.erase(it);
}
}
}
}
printf("%d\n",ans);
}
return ;
}
上一篇:BZOJ 2467: [中山市选2010]生成树(矩阵树定理+取模高斯消元)


下一篇:算法与数据结构题目的 PHP 实现:栈和队列 由两个栈组成的队列