开发笔记:[CF1267J]JustArrangetheIcons贪心

篇首语：本文由编程笔记#小编为大家整理，主要介绍了[CF1267J] Just Arrange the Icons - 贪心相关的知识，希望对你有一定的参考价值。

Description

你的手机上有 $ n $ （$ 1 $ $le n $ $le 2 imes 10^6 $）个软件，其中第 $ i $ 个软件的类型为 $ c_i $，你需要在可以自由选择每页大小 (s) 的情况下，求出最小的页码数量 $ k $，使得每一页都装满或只空一个，并且每一页的所有软件类型都相等，求最小的页码 $ k $。

Solution

首先，对于确定的 (s) 和某种的个数 (c)，如果满足 (c in [x(s-1),xs])，则可以用 (x) 块屏幕装下它

对于

变形为

如果其中的确包含一个整数，即 (x‘=lceil l
ceil le r)，取 (x=x‘) 即可

于是可以简化为 (x=[frac {c-1} s]+1)，再利用上方条件进行合法性检查

于是我们考虑暴力枚举每页大小，但是每页大小是不能超过种类数最小值 (+1) 的

设种类数为 (p)，则复杂度为 (O(p min(c))=O(p frac n p)=O(n))

#include
using namespace std;
#define int long long
const int N = 2000005;
int n,c[N],s,ans=1e18;
signed main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
cin>>n;
ans=1e18;
for(int i=1;i<=n;i++) c[i]=0;
for(int i=1;i<=n;i++) {
int x;
cin>>x;
c[x]++;
}
int p=0;
vector vec;
for(int i=1;i<=n;i++) if(c[i]>0) p++, vec.push_back(i);
if(p==0) {
cout<<0< continue;
}
int lim=n/p+1;
for(int s=1;s<=lim;s++) {
int sum=0;
for(int j=1;j<=p;j++) {
int i=vec[j-1];
if(c[i]==0) continue;
int x=(c[i]-1)/s+1;
if(x*(s-1)>c[i]|| c[i]>x*s) goto E;
sum+=x;
}
ans=min(ans,sum);
E:s=s;
}
cout< }
}