分组

最多的小组最少很明显第一反应是二分，不过在二分之前我们先考虑一下什么情况下不存在。$\backslash \backslash$ ①总共人数少于分组人数②分组人数少于不同声部数量。$\backslash \backslash$ $-1-1$的情况考虑完之后，我们再考虑一下接下来两种特殊的情况:$\backslash \backslash$ 1.$n==mn==m$ 此时只有一种分配方式，得到的也只有一种解就是1$\backslash \backslash$ 2.$k==mk==m$ 不同声部的数量和要分配组数相等，很显然的我们得出最优解是最多数量的那一类声部 现在特殊情况都已经考虑清楚了，如果是上述以外的情况，我们就直接二分一下最优值即可，然后本题其实常数很小，我们可以直接暴力枚举$ii$来做$i\in [2,maxn]i\in [2,maxn]$，$checkcheck$的时候只要判断一下是否分的组数会$>m>m$即可。

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<iomanip>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 


# define eps 1e-9
# define fi first
# define se second
# define ll long long
# define int ll
// cout<<fixed<<setprecision(n) 
using namespace std;
   
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=1e9+7;
const int MAX=3e6+10;
const int Time=86400;
const int X=131;
const int inf=0x3f3f3f3f;
const double PI = 1e-4;
double pai = 3.14159265358979323846; 

int n,m,a[MAX],ans,k,maxn;
int s[MAX];

bool check(int x){
	 int sum = 0;
     for(int i = 0 ; i < k ; i ++ )
      sum+=s[i] / x + (s[i] % x != 0);
	  
	 return sum <= m; 
}

signed main(){  
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0 ; i < n ; i ++ ) cin >> a[i] ;
    sort(a,a+n);
    int sum = 1;
    for(int i = 1 ; i < n ; i ++ )
     if(a[i] == a[i-1]) sum++;
      else s[k++] = sum,sum = 1;
      s[k++] = sum;
    if(n < m || m < k){
		cout<<-1;
		return 0; 
	}
	if(n == m){
		 cout<<1;
		 return 0;
	}
	if(k == m){
		 
		  for(int i = 0 ; i < k ; i ++ )
		   ans = max(ans,s[i]);
		
		 cout<<ans;
		 return 0;
	}
	for(int i = 0 ; i < k ; i ++ )
	 maxn = max(maxn,s[i]);
	for(int i = 2 ; i <= maxn ; i ++ )
	  if(check(i)){
	  	  cout<<i;
	  	  return 0;
	  }
	  cout<<-1;
    return 0; 
}
/*
mid = 2
2 3
*/