题面

概述：有$n$张卡片，每张卡片有一个数值$r_i$。每回合用一张卡片$i$去攻击另一张卡片$j$。如果$r_i>r_j$，则卡片$j$退出。每张卡片最多发起一次进攻，求若干回合后未退出卡片的数量最小。

#include<bits/stdc++.h>
using namespace std;
int n,a[100001],b[100001],ma;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[a[i]]++;
	}
	for(int i=1;i<=100000;i++)
	{
		ma=max(ma,b[i]);
	}
	cout<<ma;
	return 0;

思路：当有三只怪物战力分别为$1$，$2$，$3$时，最优方案为$2$打$1$，$3$打$2$。

所以，得出结论：第$k$大战力要打第$k-1$大战力。

此时有两种情况：

1. 第$k$大战力的怪物数（$x$）大于等于第$k-1$大战力的怪物数（$y$）。

此时攻击完后有$x$只第$k$大战力的怪物。

2. 第$k$大战力的怪物数（$x$）小于第k-1大战力的怪物数（$y$）。

此时攻击完后有$x$只第$k$大战力的怪物和$y-x$只第$k-1$大战力的怪物，共$y$只。

由于第$k-1$大战力的怪物比第$k$大战力的怪物战力小，则一定比$k+t(t>=1)$大战力的怪物战力小。

综上所述，攻击完一轮后共有$max(x,y)$只战力小于等于第$k$大战力的怪物。

一直往后推，得答案最小为$max(shu_1,shu_2,......,shu_{100000})$（$shu_i$表示战力为$i$的怪物数）。

测试记录