CF1267J Just Arrange the Icons

题目大意
多测。
给你个应用程序，每一个应用程序都有一个类别，类别可以相同。

你可以自己定义与的数量，分别表示屏幕的数量和每个屏幕的容量，你需要把每个应用都放到屏幕上，要求每个屏幕只能放一种程序并且数量要么等于，要么等于。
## 贪心思路
定义数组表示应用类型为的数量。首先注意到最大只能是，不然就算把最大的单独放到屏幕里也无法满足要求，基于次我们发现了一个时间复杂度是的算法。

先枚举，在枚举所有的，检测一下能否满足要求，即所有的能否通过屏幕容量为这一条件成立。
证明
我们发现交上去过了，这是为什么呢，我们来证明一下。首先这个代码的时间复杂度是的，其中是不同的的种类数，那最坏情况就是所有都相等，这样可以使前半部分最大，也就是，也就是的了。
代码

#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e6+5; int T,n,a[N],b[N]; struct node{ int x,id; }; node c[N]; bool flag[N]; bool f(int n,int s){ if(s==1) return true; int mi=(n+s-1)/s; int mx=n/(s-1); return mi<=mx; } int ff(int n,int s){ if(s==1) return n; return (n+s-1)/s; // 最少屏幕数就是ceil(n/s) } signed main(){ scanf("%lld",&T); while(T--){ int t=0; int mi=LLONG_MAX; scanf("%lld",&n); for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); if(flag[a[i]]==0){ flag[a[i]]=1; c[++t].id=a[i]; b[a[i]]=t; c[t].x=1; }else{ c[b[a[i]]].x++; } } for(int j=1;j<=t;j++){ mi=min(mi,c[j].x); } int res=LLONG_MAX; for(int s=1;s<=mi+1;s++){ int ans=0; bool flag2=true; for(int j=1;j<=t;j++){ if(f(c[j].x,s)==true){ ans+=ff(c[j].x,s); }else{ flag2=false; break; } } if(flag2==true) res=min(res,ans); } printf("%lld\n",res); for(int j=1;j<=t;j++){ flag[c[j].id]=0; b[c[j].id]=0; c[j]={0,0}; } } return 0; }