[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(s-1) le c le xs ]

变形为

[l=frac c s le x le frac c {s-1}=r ]

如果其中的确包含一个整数，即 (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 <bits/stdc++.h>
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 <int> vec;
        for(int i=1;i<=n;i++) if(c[i]>0) p++, vec.push_back(i);
        if(p==0) {
            cout<<0<<endl;
            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<<ans<<endl;
    }
}