zcmimi's blog
查看原题

点击跳转

先排序

从小到大添加

如果有以a_i-1的组,那么a_i必然添加在目前以a_i-1结尾的组的末尾

否则新建一个组

可以使用 桶+堆 实现

#include<bits/stdc++.h>
#include<bits/extc++.h>
const int N=100011;
int n,a[N];
std::priority_queue<int,std::vector<int>,std::greater<int>>q[N];
__gnu_pbds::cc_hash_table<int,int>T;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    std::sort(a+1,a+n+1);
    int t=0;
    for(int i=1;i<=n;++i){
        if(!T[a[i]])T[a[i]]=++t;
        if(q[T[a[i]-1]].empty())q[T[a[i]]].push(1);
        else q[T[a[i]]].push(q[T[a[i]-1]].top()+1),q[T[a[i]-1]].pop();
    }
    int ans=n;
    for(int i=1;i<=t;++i)if(!q[i].empty())ans=std::min(ans,q[i].top());
    printf("%d\n",ans);
}
LG 4447 [AHOI2018初中组]分组
comment评论
Search
search