牛牛找子集题解

题意：牛牛和牛妹在玩一个游戏，在他们面前有n个数。牛妹说出一个数字k，牛牛就要从这些数中找到多个由k个数字组成的子集，每个数字有且只能使用一次，并且这些子集是完全相同的，子集内部元素可以相同，完全相同的子集是指两个集合里的元素及其个数都是相同的。
游戏胜利的目标是：找到满足游戏规则，且数量最多的子集。
牛牛特别想赢得游戏，所以他想请你帮他写一个程序，找到能够满足游戏胜利条件的子集，并且输出这个子集。如果有多个子集满足条件，输出字典序最小的即可。

时间复杂度: 空间复杂度:
解题思路：
二分+贪心解法。
其实题目的意思可以理解为：给定一个长度为n的数组,从中找一个长度为k的元素可以重复的子集，并且可以把这个子集从数组中不断的删除，直到不能够再删除为止。所以我们只要确保最小化该数组(被不断地删除后)，并且输出最小的字典序子集即可。
二分策略：我们可以对删除的次数进行二分操作。对于二分内的条件，我们可以这么思考，首先我们先假设可以删除多少次，那么我们就可以计算每个数在数组中出现的次数，然后将所有出现的次数和与数组的大小进行比较，以此来二分求得到最合适的删除次数。然后我们需要输出字典序最小的子集，我们可以根据得到的删除次数和每个数字的次数来这两个条件来确定一个数字是否满足条件，从小到大遍历即可。

    /**
     * 返回找到能够满足游戏胜利条件的子集，如果有多个子集满足条件，返回字典序最小的即可。
     * @param n int整型 代表数字的数量
     * @param k int整型 代表子集的大小
     * @param s int整型vector 代表数字数组
     * @return int整型vector
     */
    vector<int> solve(int n, int k, vector<int> &s)
    {
        const int maxn = 1e5 + 100;
        int pos[maxn] = {0};
        for (int i = 0; i < n; i++)
            pos[s[i]]++;

        int l = 1, r = 1e5 + 10;
        int ans = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            int sum = 0;
            for (int i = 1; i <= 1e5; i++)
                sum += pos[i] / mid;
            if (sum >= k)
                l = mid + 1, ans = mid;
            else
                r = mid - 1;
        }
        // printf("%d\n", ans);
        vector<int> result;
        int tot = 0;
        for (int i = 1; i <= 1e5 + 10; i++)
        {
            for (int j = 1; j <= pos[i] / ans && ++tot <= k; j++)
            {
                result.push_back(i);
            }
        }
        return result;
    }