特定の配列から作ることができる特定のサイズの類似グループの最大数

Question

私は、必ずしも一意ではなく、グループのサイズの配列を与えられています。 $ b $ で配列を表し、グループのサイズは $ a $ です。

まったく同じ内容とサイズ $ a $ の最大数を見つける必要があります。 $ b $ 。要素がグループ内で使用されると、それは使い果たされます。要素がまだ $ b $ で利用可能である限り、グループは複数の要素を持つことができます。

例：

1. 入力配列が $ \ {1,2,3,1,2,3,4 \} $ 、およびグループサイズが $ 3 $ 行えるグループの最大数は $ 2 $ です。 $ \ {1,2,3 \} $ と $ \ {1,2,3 \} $ 。
2. 入力配列が $ \ {1,3,3,3,6,3,10 \} $ の場合、およびグループサイズは $ 4 $ 行えるグループの最大数は $ 1 $ です。 $ \ {1,3,3,3 \} $ 。

これまでに試したことは、いくつかの方程式を留めることです（下記の）、その後、それらを解決するためのアルゴリズムを思いつくのに苦労しています。

$ f_1 $ $ b_1 $ 、 $ F_2 $ $ b_2 $ などの頻度である $ b_n $ 。 $ b_1 \ dots b_n $ は、配列 $ b $ 。

今度は $ n_1、n_2、\ dots n_i $ を選択する必要があります。

1. $ n_1 + n_2 + \ dots + n_i= a $
2. $ k \ cdot n_1 \ leq f_1 \ text {、} k \ cdot n_2 \ leq f_2 \ text {、} \ dots \ text {、} k \ cdot n_i \ LEQ F_I $
3. $ K $ はグループの数です。最大化する必要があります。
$ b $ の長さは、 $ 10 ^ 5 $ と $ A $ は、 $ 10 ^ 5 $ と同じ大きさにすることもできます。

問題への欲張りや動的なアプローチを見つけてください。

Answer 1

機能 $$ f：\ mathbb {n} \ ritarrow \ {0,1 \}：f（k）= \ begin {ケース} 1; ＆\ text {サイズの解決策がある場合、$ k $、} 0; ＆\ text {そうでなければ} \ end {ケース} $$ サイズの解がない場合は $ k $ の解がない場合は、size $ k + 1 $の解はありません。 。つまり、Interval $ [1、| B |] $ を出力し、最大の $ k $ を出力します。 $ k $ のソリューションがあります。これにより、 $ o（\ log | b |）$ ancomeの決定問題に問題が発生しました。

$ k $ の固定値は、欲張りな解決策で十分です。 $ f_i $ のコピーがある場合は、 $ b_i $ のコピーで、各セットには最大< SPAN CLASS="math-container"> $ \ left \ lfloor \ frac {f_i} {k} \ right \ rfrooor $ 。そのため、SPAN CLASS="Math-Container"> $ K $ の解決策があります。 $$ \ sum \ limits_ {i= 1} ^ {n} \ left \ lfloor \ frac {f_i} {k} \ right \ rforor \ geq a。$$

運動として、欲張り解が最適であることを証明するようにしてください。実行時間は $ o（| b | log | b |）$