UVA Live 7146 Defeat the Enemy——STL

UVA Live 7146 Defeat the Enemy——STL

Long long ago there is a strong tribe living on the earth. They always have wars and eonquer others.One day, there is another tribe become their target. The strong tribe has decide to terminate them!!!There are m villages in the other tribe. Each village contains a troop with attack power EAttacki,and defense power EDefensei. Our tribe has n troops to attack the enemy. Each troop also has theattack power Attacki, and defense power Defensei. We can use at most one troop to attack one enemyvillage and a troop can only be used to attack only one enemy village. Even if a troop survives anattack, it can’t be used again in another attack.The battle between 2 troops are really simple. The troops use their attack power to attack againstthe other troop simultaneously. If a troop’s defense power is less than or equal to the other troop’sattack power, it will be destroyed. It’s possible that both troops survive or destroy.The main target of our tribe is to destroy all the enemy troops. Also, our tribe would like to havemost number of troops survive in this war.

题意：有两个集合x和y，集合中的每个元素都有两个指标atk和def，一个元素能消灭另一个元素的条件是这个元素的atk大于另一个元素的def，反之同样成立，也就是说这两个元素可以同归于尽，问集合x在完全消灭集合y的前提下能存活多少元素，若无法消灭y输出-1

思路：贪心思路好推，但是multiset优化有点难想，主要是以前接触的太少

multiset中存放的集合x的元素的def

大体流程为：对x按照atk从大到小排序，对y按照def从大到小排序，遍历y，对于每一个yi，将满足xj.atk大于等于yi.def的xj筛选出来，将筛选出的xj.def插入到multiset中，如果此时集合为空，那么说明无解，因为此时的yi没有来自集合x的元素可以战胜它，然后在multiset中lowerbound找yi.atk，如果找到了大于等于yi.atk的元素，那就说明yi可以被x中的元素无损消灭，如果找不到，那么就贪心的拿multiset中最小的元素来消灭yi

#include #include #include #include #include using namespace std;const int maxn = 1e5+5;struct Date { int atk, def;}x[maxn], y[maxn];bool cmpatk(const Date& x, const Date& y) { return x.atk > y.atk;}bool cmpdef(const Date& x, const Date& y) { return x.def > y.def;}int main() { int T, n, m; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d %d", &x[i].atk, &x[i].def); for (int i = 1; i <= m; i++) scanf("%d %d", &y[i].atk, &y[i].def); sort(x+1, x+1+n, cmpatk); sort(y+1, y+1+m, cmpdef); int ans = 0; multiset s; multiset::iterator it; for (int i = 1, j = 1; i <= m; i++) { for (; j <= n && x[j].atk >= y[i].def; j++) s.insert(x[j].def); if (s.empty()) { ans = n+1; break; } it = s.upper_bound(y[i].atk); if (it == s.end()) { ans++; s.erase(s.begin()); } else s.erase(it); } printf("Case #%d: %d\n", kase, n-ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。