牛客プログラミングサミットS 1第11回-黄金&ダイヤモンドC.牛牛探サブセット

牛客プログラミングサミットS 1第11回-黄金&ダイヤモンドC.牛牛探サブセット
タイトルリンク
タイトルの説明
牛と牛の妹はゲームをしていて、彼らの前にn個の数があります.牛妹は1つの数字kを言って、牛はこれらの数の中からkの数字からなる複数のサブセットを見つけて、各数字は1回しか使用できなくて、しかもこれらのサブセットは完全に同じで、サブセットの内部の要素は同じで、完全に同じサブセットは2つのセットの中の要素とその数が同じであることを指します.ゲームの勝利の目標は、ゲームのルールを満たし、最も多くのサブセットを見つけることです.牛は特にゲームに勝ちたいので、ゲームの勝利条件を満たすサブセットを見つけて、このサブセットを出力するプログラムを書いてもらいたいと思っています.複数のサブセットが条件を満たしている場合は、辞書シーケンスを最小に出力すればよい.
例1
入力

12,5,[1,1,1,1,1,1,2,2,2,2,2,2]

しゅつりょく

[1,1,1,2,2]

例2
入力

7,3,[1,2,3,2,4,3,1]

しゅつりょく

[1,2,3]

白給問題、私の2点は本当に悪くて、いつもこのようなやり方を無視して、この問題は裸の2点で、分けることができる最大のグループ数を探して、それから最大のグループ数で出力すればいいので、選んだ数の数はk k k kより大きいかもしれないことに注意して、だから最後にr e s i z e resize resizeを要して、サンプルの1は1つの特例で、ACコードは以下の通りです:

class Solution {
public:
    /**
     *                  ，           ，          。
     * @param n int          
     * @param k int          
     * @param s int  vector       
     * @return int  vector
     */
    vector<int> solve(int n, int k, vector<int> &s){
        vector<int>ans;
        map<int,int>mp;
        for(auto i:s) mp[i]++;
        int l=1,r=n;
        while(l<=r){
            int mid=l+r>>1,siz=0;
            for(auto i:mp){
                siz+=i.second/mid;
            }
            if(siz>=k) l=mid+1;
            else r=mid-1;
        }
        for(auto i:mp){
            for(int j=0;j<i.second/r;j++) ans.push_back(i.first);
        }
        ans.resize(k);
        return ans;
    }
};