题解 | #牛牛国的战争#

#include<bits/stdc++.h>

using namespace std;

int T;
const int N=1e5+10;
struct ty{
    int x,y;
}a[N],b[N];

bool cmp1(ty a,ty b)
{
    if(a.x == b.x)return a.y < b.y;
    return a.x > b.x;
}//国王的队伍攻击力从大到小，相同时防御力值反之

bool cmp2(ty a,ty b)
{
    if(a.y == b.y)return a.x < b.x;
    return a.y > b.y;
}//敌军的队伍防御力从大到小，相同时攻击力值反之

int n,m;
int cnt=1;
int ans;

void solve()
{
    multiset<int> q;
    cin >> n >> m;
    ans=n;
    int i,j;
    for(i=1;i<=n;i++){
        cin >> a[i].x >> a[i].y;
    }
    for(i=1;i<=m;i++){
        cin >> b[i].x >> b[i].y;
    }
    sort(a+1,a+1+n,cmp1);
    sort(b+1,b+1+m,cmp2);
    for(i=1,j=1;i<=m;i++){
        while(j<=n&&a[j].x>=b[i].y){
            q.insert(a[j].y);
            j++;
        }//国王队伍[j]的攻击力值大于等于敌军[i]的防御力值的编号push进q
        auto it=q.upper_bound(b[i].x);//寻找录入q中防御力值大于敌军[i]的位置
        if(it != q.end()){
            q.erase(it);//由于每只队伍最多只能参加一次
        }else{
            if(q.empty()){
                printf("Case #%d: -1\n",cnt);
                cnt++;
                return;//若q为空（即无部队可参与）则输出-1
            }else{
                ans--,q.erase(q.begin());//若q不为空，则选择首位（即攻击力当下max，防御力min的队伍）与其消除
            }
        }
    }
    printf("Case #%d: %d\n",cnt,ans);
    cnt++;
    return;
}


int main()
{
    cin >> T;
    while(T--){
        solve();
    }
}