题解：P10351 [PA2024] Liderzy

· · 题解

洛谷 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;
}