Link

洛谷 & Codeforces

Tag

洛谷：暂无标签

Codeforces：binary search，data structures，greedy，math，sortings

Difficulty Level

洛谷：$普及/提高-$

Codeforces：$1500$

Solution

一个易得的想法是先处理出不同数字出现的次数，显然删掉一个数就是使这个数的次数减 $1$，于是将问题转化为使这些次数都相等最少需要减 $1$ 的数量。

设最后我们将所有次数都转化为 $x$。那么对于大于 $x$ 的次数，我们需要将其减到 $x$；对于等于 $x$ 的次数不操作；对于小于 $x$ 的，我们只能将其减到 $0$。

我们枚举每个数字的次数，通过上述方式将所有次数转化为该数字的次数并计算代价，最终答案为代价的最小值。

显然，直接这样做是 $O(n^2\log n)$ 的。考虑排序后用前缀和维护，将复杂度优化到 $O(n\log n)$。

Code

#include
#include
#include
using namespace std;
int n,ans=0x3f3f3f3f;
int a[200010];
int p[200010],tot;
int s[200010];
void work()
{
	tot=0,ans=0x3f3f3f3f;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
		if(a[i-1]!=a[i])
			p[++tot]=1;
		else
			p[tot]++;
	sort(p+1,p+tot+1);
	for(int i=1;i<=tot;i++)
		s[i]=s[i-1]+p[i];
	for(int i=1;i<=tot;i++)
		ans=min(ans,s[i-1]+(s[tot]-s[i])-(tot-i)*p[i]);
	printf("%d\n",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
		work();
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Submission

Codeforces Submission