How can we effectively defeat the enemy in UVALive7146 challenge?

本文共计830个文字，预计阅读时间需要4分钟。

题目链接+题目+链接题目+见链接题目解析+知识点：贪婪，STL。首先，要确保我方军队能消灭对方军队，因为只有这样才行动。所以，我们需要从大到小排序攻击力，从小到大排序防御力，然后从大到小遍历。使用我方军队所对应的攻击力去消灭对方军队。

题目链接

题目

见链接。

题解

知识点：贪心，STL。

首先要保证我方军队能消灭对方军队才行，因此只要我们按攻击力从大到小排，对方按防御力从大到小排，从大到小遍历，用我方所有攻击力大于敌方目前防御力军队中的一个打，就能保证对方小的防御力不会先把我方大的攻击力用掉，导致对方大的防御力没有办法消灭，即能消灭就一定消灭，不能就一定不能返回 \(-1\)。

现在考虑保证我方被消灭最少，发现如果在我方攻击力大于对方防御力的军队里面选，一定优先选择防御力刚好大于对方攻击力的军队，这样就可以保证大的防御力能保留，小的防御力不会被消灭；但如果最大的防御力都小于等于对方攻击力，那一定选择防御力最小的军队打，因为既然都会同归于尽，那么就让大的防御力保留，把最小的防御力同归于尽，保证后面有足够的防御力。因此我们这时候需要一个容器能够排序，查询，删除，插入，可以有相同元素，那么就要选择 \(multiset\) 存储我方军队防御力。

于是，每次先把大于等于的军队放入多重集，如果没有则返回 \(-1\) 。然后查找一个刚好防御力大于其攻击力的军队打，否则就用防御力最小的打，然后军队存活数量减一。

时间复杂度 \(O((n+m) \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h> #define ll long long using namespace std; struct node { int atk, def; }a[100007], b[100007]; bool solve() { int n, m; cin >> n >> m; for (int i = 0;i < n;i++)cin >> a[i].atk >> a[i].def; for (int i = 0;i < m;i++)cin >> b[i].def >> b[i].atk; sort(a, a + n, [&](node a, node b) {return a.atk > b.atk;}); sort(b, b + m, [&](node a, node b) {return a.def > b.def;}); int cnt = n; multiset<int> ms; for (int i = 0, j = 0;j < m;j++) { while (i < n && a[i].atk >= b[j].def) ms.insert(a[i++].def); if (ms.empty()) return false; auto it = ms.upper_bound(b[j].atk); if (it == ms.end()) { ms.erase(ms.begin()); cnt--; } else ms.erase(it); } cout << cnt << '\n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1, cnt = 1; cin >> t; while (t--) { cout << "Case #" << cnt++ << ":"; if (!solve()) cout << -1 << '\n'; } return 0; }