题目翻译:

很久很久以前，地球上生活着一个强大的部落。他们经常发动战争，征服其他部落。

有一天，另一个部落成为了他们的目标。这个强大的部落决定要消灭他们！！！

这个被盯上的部落拥有 m 个村庄，每个村庄都有一支军队，这支军队具备攻击力 EAttacki 和防御力 EDefensei。我们的部落有 n 支军队可以用来进攻敌人，每支军队同样拥有攻击力 Attacki 和防御力 Defensei。我们最多只能用一支军队进攻一个敌人村庄，且一支军队只能用于进攻一个敌人村庄。即便某支军队在一次进攻中存活下来，也不能再用于另一次进攻。

两支军队之间的战斗规则非常简单：双方会同时用各自的攻击力攻击对方。如果一支军队的防御力小于或等于对方军队的攻击力，那么这支军队就会被摧毁。战斗中可能出现双方都存活，或者双方都被摧毁的情况。

我们部落的主要目标是摧毁敌人的所有军队，同时希望在这场战争中让我方存活的军队数量尽可能多。

输入

输入的第一行给出测试用例的数量 T。接下来是 T 个测试用例。每个测试用例以两个数字 n 和 m 开头，分别表示我方军队的数量和敌人村庄的数量。随后的 n 行，每行包含两个数值 Attacki 和 Defensei，代表我方某支军队的攻击力和防御力。再接下来的 m 行描述敌人的军队，每行包含两个数值 EAttacki 和 EDefensei，代表敌人某支军队的攻击力和防御力。

输出

对于每个测试用例，输出一行内容：“Case #x: y”，其中 x 是测试用例的编号（从 1 开始），y 是我方军队在这场战争中最多能存活的数量。如果无法摧毁敌人的所有军队，则输出 “-1”。

Limits: 1 ≤ T ≤ 100, 1 ≤ n,m ≤ 1e5, 1 ≤ Attacki,Defensei,EAttacki,EDefensei ≤ 1e9,

Sample Input 2 3 2 5 7 7 3 1 2 4 4 2 2 2 1 3 4 1 10 5 6

Sample Output Case #1: 3

Case #2: -1

下面这句话是重点:

如果一支军队的防御力小于或等于对方军队的攻击力，那么这支军队就会被摧毁。战斗中可能出现双方都存活，或者双方都被摧毁的情况。

思路: 首先至少要让我方军队能消灭对方(同归于尽也行)才行,即我方战斗力>=地方防御力.然后为了让我方死亡人数少,要让地方的攻击力<我方防御力,即我方防御力>地方防御力.

然后又用到了一个贪心策略:先难后易(先把难的敌人解决了).因为如果某一个战友能把难的敌人解决,就一定能把排在后面的简单(防御力低)的敌人解决,这样新建一个multi集合,就可以把符合当前高要求的加入,这个集合也能满足后面低要求的,就不用每次找完后,又舍弃,然后又重新找.

如何实现先把难的敌人解决? =>把敌人按防御力(从大到小)排序

如何实现找到我方符合当前要求(能战胜当前敌人,即攻击力>=对方防御力)的战友,且不重不漏? =>把我方按战斗力(从大到小)排序,顺序遍历即可

为什么要从大到小排? =>使遍历的索引从1 ++,而不是从最后一个 --,更清晰直观

代码&思路:

#include <algorithm>
#include<iostream>
#include<set>
using namespace std;
#define N 100010
struct duiyou {
    int attack, defense;
    bool operator < (const duiyou &other) const {
        return attack>other.attack;
    }
}dui[N];
struct diren {
    int attack,defense;
    bool operator < (const diren &other) const {
        return defense>other.defense;
    }
}di[N];
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t,n,m;cin>>t;
    for(int i=1;i<=t;++i) {
        cin>>n>>m;
        for (int j=1;j<=n;++j) {
            cin>>dui[j].attack>>dui[j].defense;
        }
        for (int j=1;j<=m;++j) {
            cin>>di[j].attack>>di[j].defense;
        }
        sort(dui+1,dui+1+n);
        sort(di+1,di+1+m);
        multiset<int> ms;//储存能打败当前敌人的战友,  那么也是能打败之后敌人的
        int k=1,ans=n;//ans=我方总人数
        for (int j=1;j<=m;++j) {//j遍历每一个敌人,要保证能打败每一个敌人
            while (k<=n && dui[k].attack>=di[j].defense) {
                ms.insert(dui[k].defense);++k;//k遍历我方,找到能符合要求的,加入其defense,是为了后面能找到符合要求(打败敌人)中防御力刚好打过敌人的,做到贪心(利用最大化)
            }
            if (ms.empty()) {ans=-1;break;}//每一个能打败敌人,去了也是送死,输出-1,即不可能
            auto it=ms.upper_bound(di[j].attack);//找第一个防御力>当前敌人的,即保证自身存活
            if (it==ms.end()) {it=ms.begin();--ans;}//upper_bound返回end,代表没找到,只能同归于尽,我方战友数-1;然后为了利用最大化,选当前防御力最低的去同归于尽
            ms.erase(it);//一个我方只能攻击一个敌人
        }
        cout<<"Case #"<<i<<": "<<ans<<'\n';
    }
    return 0;
}