题解 | #牛牛国的战争#

//面对每一次的敌人，如果有可以将敌人打到的军队那么选刚好防御力够存活下来的那一个。
//如果能打到敌人但是确是去送死的话，那么选防御力最差的那一个。
//如果不能打倒敌人那么直接宣布失败就可以。
//首先使用结构体数组对其进行相应的排序，然后将攻击力满足的防御力放入multiset（利用set里面默认从小到大排序的性质）里面，通过自带的二分查找的函数找到相应的防御力。（这一步直接将攻击力与防御力分开的做法是方便代码编写以及提升速度的关键）。
#include <bits/stdc++.h>


using namespace std;
#define int long long
struct Node {
    int a,d;
};
const int maxn = 100000+10;
int cnt = 1;

Node niu[maxn];
Node di[maxn];
//对于敌人来说，要首先按照防御力从大到小排序，然后按照攻击力从小到大排序
bool comp1(Node n1, Node n2) {
    if (n1.d==n2.d) return n1.a<n2.a;
    return n1.d>n2.d;
}
//对于牛牛国部队来说首先按照攻击力从大到小排序，然后按照防御力从小到大排序。
bool comp2(Node n1, Node n2) {
    if (n1.a==n2.a) return n1.d<n2.d;
    return n1.a>n2.a;
}

void solve() {
    int n, m;
    
    multiset<int> ms;
    cin>>n>>m;
    int ans = n;
    for (int i=0;i<n;i++) {
        cin>>niu[i].a>>niu[i].d;
    }
    for (int i=0;i<m;i++) {
        cin>>di[i].a>>di[i].d;
    }
    sort(di, di+m, comp1);
    sort(niu, niu+n, comp2);
    for (int i=0, j=0;i<m;i++) {
        //将攻击力满足的牛牛国的军队的防御力全部放进multiset里面。
        while (j<n&&niu[j].a>=di[i].d) {
            ms.insert(niu[j].d);
            j++;
        }
        if (ms.empty()) {
            printf("Case #%d: %d\n", cnt, -1);
            return ;
        }
        //二分去查找对应的防御力
        multiset<int>::iterator it = ms.upper_bound(di[i].a);
        if (it==ms.end()) {
            ans--;
            //从小到大排序的，删除第一个。
            ms.erase(ms.begin());
        } else {
            ms.erase(it);
        }
    }
    printf("Case #%d: %d\n", cnt, ans);
    return ;
}

signed main() {
    int T;
    cin>>T;
    while(T--) {
        solve();
        cnt++;
    }
    return 0;
}