I http://acm.hust.edu.cn/vjudge/contest/view.action?cid=84975#problem/I
题意：我方有n个士兵，敌方有m个士兵，每个士兵有攻击力和防御力，我方一个兵只能选择对方一个兵去战斗，即使我方幸存了也不能再去和别的敌人战斗，一场战斗中防御力小于等于对方攻击力的兵会死，我们需要选出一个方案使得杀死对面所有兵，且我们存活的兵尽量多。
解法：先把我军按照攻击力从大到小排序，敌军按照防御力从大到小排序，然后依次枚举敌军士兵，对每个敌军士兵，我们把攻击力大于等于其防御力的都存到map中，存我军的防御力。map中的都一定能杀死对手。所以我们在map中二分出第一个防御力大于敌军攻击力的，那么选择他可以使得幸存的人数多一个，并且防御力最节省。贪心。
//#define txtout
//#define debug
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int M=1e5+;
map<int,int> mp;
map<int,int>::iterator it;
struct G{
int attack,defense;
}our[M],his[M];
int n,m;
bool cmp_defense_de(const G &a,const G &b){
return a.defense>b.defense;
}
bool cmp_attack_de(const G &a,const G &b){
return a.attack>b.attack;
}
int solve(){
sort(our,our+n,cmp_attack_de);
sort(his,his+m,cmp_defense_de);
mp.clear();
int our_id=;
int result=;
for(int i=;i<m;i++){
while(our_id<n&&our[our_id].attack>=his[i].defense){
mp[our[our_id].defense]++;
our_id++;
}
if(mp.empty()) return -;
it=mp.upper_bound(his[i].attack);
if(it==mp.end()){
it=mp.begin();
}
else{
result++;
}
if(it->second==){
mp.erase(it);
}
else{
mp[it->first]--;
}
}
result+=n-our_id;
for(it=mp.begin();it!=mp.end();it++){
result+=it->second;
}
return result;
}
int main(){
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
int t;
while(~scanf("%d",&t)){
int cas=;
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%d%d",&our[i].attack,&our[i].defense);
}
for(int i=;i<m;i++){
scanf("%d%d",&his[i].attack,&his[i].defense);
}
printf("Case #%d: %d\n",cas++,solve());
}
}
return ;
}
end