自动搬运

查看原文

来自洛谷，原作者为

	HaneDaniko 濯净大地的浑浊。

搬运于2025-08-24 22:57:08，当前版本为作者最后更新于2024-04-19 17:27:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

洛谷 P10351

题意简述

找到一个序列每个划分都有主元素的最少划分。

主要思路

这道题使用贪心。

首先我们需要知道，假如一个划分内的主元素出现次数为 $n$，那么这个划分内的最大承载元素就为 $2n-1$，可以证明假如再添加一个元素就不存在主元素了。

那么，对于一个出现次数为 $n$ 的数字，直接将它作为划分的主元素和拆成两部分比起来，直接划分只有一个减一，而拆成两部分的式子中有两个减一，其余部分不变。因此我们可以归纳出，直接将出现次数较大的数作为一个划分的主元素是最优的。

因此，这道题的主要思路就是：

1. 统计序列中每个元素的出现次数。

2. 将出现次数从小到大排序，根据贪心，每次取出出现次数最大的数作为主元素，统计该划分内的总数。

3. 当所有划分的总数大于等于 $n$ 后，当前的全部划分即为答案。

代码实现

#include<bits/stdc++.h>
using namespace std;
struct num{
	int tot;
	bool operator<(const num &A)const{
		return tot>A.tot;
	}
}cnt[500001];
int n,tot,ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		if(!cnt[x].tot) tot++;
		cnt[x].tot++;
	}
	sort(cnt+1,cnt+n+1);
	tot=n;
	for(int i=1;i<=n;++i){
		if(cnt[i].tot*2-1>=tot){
			ans++;
			break;
		}
		ans++;
		tot-=cnt[i].tot*2-1;
	}
	cout<<ans;
}