Just Arrange the Icons

Created by LXC on Sun Jul 2 09:42:07 2023

https://codeforces.com/problemset/problem/1267/J

ranting: 1800

tag: greedy, implementation, math

problem

有一部手机，你可以设计m个应用图标页面，每个页面最多能放s个图标。

现在给出n个应用的种类，相同种类的图标只能放到同一个页面，一个页面必须放满图标或者恰好放s-1个图标。

问最小的m是多少。

n<=2e6

solution

s不应该大于mx = n个应用里数目最小的种类+1。否则一个页面无法放置数目最小的种类。

我们枚举s即可。随着s<=mx，n个应用里至少有mx个属于同一种类的应用。

时间复杂度$O((n-mx)*mx)$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    set<int> st;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[x]++;
        st.insert(x);
    }
    int ans = n;
    int mx = *max_element(a.begin(), a.end()) + 1;
    for (int i = 1; i <= mx; i++) {
        int t = 0;
        for (int j : st) {
            if (a[j] % i == 0)
                t += a[j] / i;
            else if (a[j] / i + a[j] % i >= i - 1)
                t += a[j] / i + 1;
            else {
                t = n;
                break;
            }
        }
        ans = min(ans, t);
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}