思路与算法

统计每个攻击防御值的出现次数，答案是最大频次。无需模拟攻击顺序。

正确性说明

每次成功攻击必须从较大值指向较小值；每只怪物最多攻击一次、最多被成功消灭一次，成功边构成若干严格下降链。每条链至多含一个给定值，故最高频次f强制至少f条链、至少f个幸存者。反之准备f条链，每一种值的卡牌各分给不同链，链内降序排列，就能覆盖全部卡牌；每条链从低端向高端执行攻击，使内部怪物先用掉攻击机会再被消灭，最终仅留链顶。链顶未攻击者可进行不改变最少存活数的失败攻击，或仅剩一只时结束。上下界相同。

复杂度

O(n+V)时间、O(V)空间，V=100000；包含整个计数数组清零。

易错点

攻击力等于防御力不能消灭。不能当Nim或SG胜负题；目标是最少幸存数量，重复最多的值而非不同值数决定答案。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> count(100001);
    int ans = 0;
    while (n--) {
        int x;
        cin >> x;
        ans = max(ans, ++count[x]);
    }
    cout << ans << "\n";
}