自动搬运

查看原文

来自洛谷，原作者为

	gongziwen [2022] CSP提高 二等奖 [2023] CSP提高 二等奖 [2024] CSP提高 二等奖

搬运于2025-08-24 23:05:31，当前版本为作者最后更新于2024-10-26 22:05:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解法很简单，直接求众数即可。

很显然，每个怪兽尽量发挥自己活着的价值，即尽量干掉一个比他攻击值小的怪兽。

很显然，攻击值越大应该越晚被干掉。

我们按攻击力从大到小分层。

那么如果都不相等，那应该只会留下攻防最大的那个。

设第 $i$ 层人数为 $a_i$.

每一层都应该会留下 $\max\{a_{i-1}-a_i,0\}$ 个怪兽。其实把这个值加起来就对了，但是还要解释一下为什么众数是对的。

我们发现是 $a_{i-1}>a_i$ 这个值就是其差，否则为 $0$.

我们直接令 $b_i=a_i-a_{i-1}$，那么就是求 $b$ 数组大于零值的和，设 $b$ 数组选出来大于零的的值为 $c$ 集合（即 $b_{c_i}>0$，且 $c$ 是极大的），那么 $a_{c_i}$ 是严格单调上升的。

所以说答案为 $\sum b_{c_i}-b_{c_{i-1}}$，即 $a_{c_{|c|}}$，又因 $a_{c_i}$ 单调上升，所以 $a_{c_{|c|}}$ 一定是 $\max\{a_{c_i}\}$，而 $c$ 是极大的，所以即为 $\max{a_i}$.

代码如下：

#include<bits/stdc++.h>
const int N=1e5+6;
int n,x,mp[N],ans;
int main()
{
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&x);
		ans=std::max(ans,++mp[x]);
	}
	printf("%d\n",ans);
	return 0;
}