【45 分】暴力检查

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int r[MAXN + 5];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> r[i];
	sort(r + 1, r + n + 1);
	for (int i = 2; i <= n; i++) // 攻击者
	{
		// 找最小的能被 i 攻击的 j
		for (int j = 1; j <= i - 1; j++)
		{
			if (r[j] != 0 && r[j] < r[i])
			{
				r[j] = 0;
				break;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += (r[i] != 0);
	cout << ans;
	return 0;
}

【100 分】双指针优化

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int r[MAXN + 5];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> r[i];
	sort(r + 1, r + n + 1);
	// 记录最小的还没有被攻击的是哪一个
	int j = 1;
	for (int i = 2; i <= n; i++) // 攻击者
	{
		if (r[j] < r[i])
		{
			r[j] = 0;
			j++;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += (r[i] != 0);
	cout << ans;
	return 0;
}

【100 分】计数排序后再双指针

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXRI = MAXN;
int n;
int r[MAXN + 5];
int cnt[MAXRI + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> r[i];
        cnt[r[i]]++;
    }
    for (int i = 1, j = 1; i <= MAXRI; i++) // 攻击者
    {
        if (cnt[i] == 0)
            continue;
        // 有 cnt[i] 个人的攻击力为 i
        // j 枚举他能攻击多少人
        int now = cnt[i]; // 记录还能打几个人
        while (j < i)
        {
            if (cnt[j] <= now)
            {
                // 攻击力为 j 的人全都被攻击了
                now -= cnt[j];
                cnt[j] = 0;
                j++;
            }
            else
            {
                // 攻击力为 j 的人被攻击了 now 个
                cnt[j] -= now;
                now = 0;
                break;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= MAXRI; i++)
        ans += cnt[i];
    cout << ans;
    return 0;
}

【100 分】找规律的众数结论

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXRI = MAXN;
int n;
int r[MAXN + 5];
int cnt[MAXRI + 5];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> r[i];
		cnt[r[i]]++;
	}
	int ans = 0;
	for (int i = 1; i <= MAXRI; i++)
		ans = max(ans, cnt[i]);
	cout << ans;
	return 0;
}