可以由给定数组进行的给定大小的最大类似组的最大数量

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 \} $ 。

到目前为止，我尝试了什么，是框架一些方程式（下面给出），但之后，我正在努力提出一个算法来解决它们。

let $ f_1 $ 是元素 $ b_1 $ ， $ F_2 $ 是元素 $ b_2 $ and $ b_n $ ，其中 $ b_1 \ dots b_n $ 是来自数组 $ b $ 。

现在我需要选择 $ n_1，n_2，\ dots n_i $ 这样
1. $ n_1 + n_2 + \ dots + n_i= $
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} \ lightarrow \ {0，1 \}：f（k）= \ begin {案例} 1; ＆\ text {如果有尺寸为$ k $的解决方案，} \\ 0; ＆\ text {否则} \结束{案例} $$ 是单调，因为如果没有大小的解决方案 $ k $ 那么没有大小的解决方案 $ k + 1 $ 。这意味着我们可以二进制搜索 $ k $ 中的值 $ [1，| b |] $ ，并输出最大的 $ k $ ，其中大小 $ k $ 。因此，我们将问题转变为带有 $ o（\ log | b |）$ 因子在运行时的决策问题。

为 $ k $ ，贪婪解决方案足够了。如果我们有 $ f_i $ 某些元素 $ b_i $ ，那么每个集合最多可以包含< Span Class=“Math-Container”> $ \ Left \ Lfloor \ FRAC {F_I} {k} \ right \ rfloor $ 这个元素的。所以我们有一个大小的解决方案 $ k $ 如果且仅当 $$ \ sum \ limits_ {i= 1} ^ {n} \ left \ lfloor \ frac {f_i} {k} \ rectle \ rfloor \ geq a。$$

作为练习，试图证明贪婪的解决方案是最佳的。运行时间可以界定在 $ o（| b | \ log | b |）。$