题解 | #Defeat the Enemy#

2014上海区域赛真题
uva一直连不上，下面的代码是我在vjudge上提交的
首先，敌人按照防御从大到小排序，先解决防御强的敌人，这里用结构体数组保存就可以了。
我方按照攻击力从大到小排序。
每次解决防御最强的敌人：先把我方攻击力高于对方防御的人加入集合s，则集合s中的人都是这次行动的可能人选。由于对方防御从大到小排序，因此只要某人进入了集合s，那么他必定也能解决后面的敌人。
下面的问题就是，在集合s中如何找到这次出站的人。
如果甲能打败敌人且能存活，乙能打败敌人却不能存活，这时候就要选择能存活的人。可以想象一下，如果选择了乙上场，那么后面甲面对新的敌人，可能存活也可能牺牲。这样在甲乙两人之中最多存活一人。而加入派甲出站，甲存活了，乙可能活也可能牺牲，这时候存活的人可能是1或2.因此，每次我们需要选择能存活的人出场。
用迭代器遍历集合s，如果指针指向了集合末尾，则说明这个敌人只能同归于尽，那就拿防御最小的人上场；如果能全身而退，就拿集合中防御大于敌人攻击的、拥有最小防御的人上场。

#include <bits/stdc++.h>
using namespace std;
typedef struct point1 we;
struct point1{//我方按照攻击从大到小排序 
    int x,y;
    bool operator < (const point1 & a) const{
        return (x>a.x);
    }
}a[100010];

typedef struct point2 en;
struct point2{//敌人按照防御从大到小排序
    int x,y;
    bool operator < (const point2 & b) const{
        return (y>b.y);
    }
}b[100010];

multiset<int> s;

int main(){
    //freopen("text.txt","r",stdin);
    ios::sync_with_stdio;cin.tie(0);cout.tie(0);
    int T;    
    cin >> T;
    for(int k=1;k<=T;k++){
        s.clear();
        cout << "Case #" << k <<": ";
        int n,m;
        cin >> n >> m;
        for(int i=0;i<n;i++){
            cin >> a[i].x >> a[i].y;
        }
        for(int i=0;i<m;i++){
            cin >> b[i].x >> b[i].y;
        }
        if(n<m)    {
            cout << "-1\n";
            continue;
        }
        sort(a,a+n);
        sort(b,b+m);
        int ans=n;
        int j=0;
        for(int i=0;i<m;i++){
            int gong=b[i].x;
            int fang=b[i].y;
            while(j<n && a[j].x>=fang){//找到我方能攻击的人，将其防御值加入集合中 
                //由于敌人防御从大到小，因此放进集合中的人，肯定还能消灭后续的人 
                s.insert(a[j].y);
                j++;
            }
            if(s.empty()){
                ans=-1;
                break;
            }
            auto it = s.upper_bound(gong);//找到能抵抗对方攻击的防御最小的人 ,换成lower_bound也可 
            if(it==s.end()){
                it=s.begin();//所有人防御都比不过对方，此时用一个防御最小的人上场 
                ans--;//同归于尽 
            }
            s.erase(it);
        }
        cout << ans << "\n";
    }
    return 0;
}