BerPhone X几乎准备发布，手机上已预装了n个应用程序。应用程序的类别描述了该应用程序的类型或主题（例如“游戏”，“业务”或“教育”）。
类别以介于1和n之间（包括1和n）的整数形式给出；第i个应用程序的类别为ci。
您可以选择m（屏幕数）和s（每个屏幕的大小）。您需要安装满足以下要求的所有n个图标（一个图标代表一个应用程序）：
·在每个屏幕上，所有图标都必须属于同一类别的应用程序（但是不同的屏幕可以包含同一类别的应用程序的图标）；
·每个屏幕必须完全填充图标（屏幕上的图标数等于s）或几乎填充图标（图标数等于s-1）。
您的任务是找到尽可能少的屏幕数m。
输入
第一行包含整数t（1≤t≤10000）-输入中测试用例的数量。然后是t个测试用例。
每个测试用例的第一行包含一个整数n（1≤n≤2×1e6）-图标的数量。第二行包含n个整数c1，c2，...，cn（1≤ci≤n），其中ci是第i个应用程序的类别。
确保输入中所有测试用例的n值之和不超过2×1e6。
输出
打印t个整数-按输入顺序遵循给定测试用例的答案。测试用例的答案是整数m-满足给定要求的所有n个图标可以放置在其上的最小屏幕数。
样例输入 Copy
3
11
1 5 1 5 1 5 1 1 1 1 5
6
1 2 2 2 2 1
5
4 3 3 1 2
样例输出 Copy
3
3
4
提示
In the first test case of the example, all the icons can be placed on three screens of size 4: a screen with 4 icons of the category 1, a screen with 3 icons of the category 1, and a screen with 4 icons of the category 5.
暴力枚举一个屏幕上有多少个应用，应用越多，屏幕越少
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<cstring> #include<cstdio> #include<iostream> #include<queue> #include<algorithm> using namespace std; typedef long long ll; template <typename Tp> void read(Tp &x){//read(n); x=0;char ch=1;int fh; while(ch!='-'&&(ch>'9'||ch<'0')){ ch=getchar(); } if(ch=='-'){ fh=-1;ch=getchar(); }else fh=1; while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+ch-'0';ch=getchar(); } x*=fh; } inline char read1()//字符串读入挂 { register char ch=getchar(); while(ch<'A'||ch>'M')ch=getchar(); return ch; } const int maxn=3e6+100; const int mod=1000000007; const int INF=0x3f3f3f; int a[maxn]; struct node{ int type; int num; node() { num=0; } }p[maxn]; int n; int s; int judge(int x){//一个屏幕应用个数 int sum=0; for(int i=1;i<=s;i++){ int z=p[i].num%x;//塞满剩下几个应用 int y=p[i].num/x;//几个屏幕 if(z==0){ sum+=y; } else if(z==x-1||(x-1-z)<=y){ sum+=(y+1); } else{ return -1; } } return sum; } int main(){ int t; cin>>t; while(t--){ cin>>n; int ma=0; for(int i=1;i<=n;i++){ read(a[i]); } sort(a+1,a+n+1); s=1; p[1].type=a[1]; p[1].num=1; for(int i = 2;i <= n;i++) { if(a[i]==p[s].type) p[s].num++; else { p[++s].type = a[i]; p[s].num = 1; } } for(int i=1;i<=s;i++){ ma=max(ma,p[i].num); } for(int i=ma;i>=1;i--){ if(judge(i)==-1){ continue; } else{ printf("%d ",judge(i)); break; } } } }