MediumRating 1639

3679. Minimum Discards to Balance Inventory

arrayhash-tablesliding-windowsimulationcounting

解題說明

Minimum Discards to Balance Inventory

題目描述：給定一個整數陣列 inventory，代表各個產品的庫存量。定義「平衡庫存」為陣列中每個元素的出現次數都相同。求最少需要丟棄多少個元素，使剩餘的庫存達到平衡。

解題思路：首先統計每個數字的出現次數。假設最終保留 g 組，每組出現 c 次，則保留的元素數為 g * c。需要丟棄的數為 n - g * c。我們需要在所有合法的 (g, c) 組合中找到使 n - g * c 最小（即 g * c 最大）的方案。

合法條件：至少有 g 個不同的數字，且每個被選中的數字至少出現 c 次。因此，先統計各數字的頻率，排序後枚舉 c，用二分搜尋或掃描找到有多少數字的頻率 >= c，即可得到 g。取所有 g * c 的最大值。

C++ 解法

複雜度分析

時間複雜度：O(n + F * log F) — 統計頻率 O(n)，排序 O(F log F)，枚舉 c 最多 O(max_freq) 次，每次二分搜尋 O(log F)。F 為不同數字的個數。

空間複雜度：O(F) — 頻率表和排序陣列。

虛擬碼

1. Count frequency of each number in inventory
2. Collect all frequencies into array, sort descending
3. For each possible count c from 1 to max_frequency:
   a. Find g = number of distinct values with frequency >= c (binary search on sorted array)
   b. Update maxKeep = max(maxKeep, g * c)
4. Return n - maxKeep

其他解法

枚舉 g（保留的組數）：固定保留 g 個不同的數字，每個數字取前 c 個。排序頻率後，取最大的 g 個頻率，c = min(這 g 個頻率)。但取最小值可能不是最優，因為可以選擇更小的 c 來容納更多的 g。

暴力枚舉所有 (g, c) 對：時間 O(F * max_freq)，在頻率不大時可行。

延伸思考

如果允許增加元素（不只是丟棄），最少操作次數是多少？
若「平衡」的定義改為「每個元素出現次數為 k 的倍數」，如何修改？
在多種平衡方案都達到最小丟棄數的情況下，如何選擇保留字典序最小的結果？

Minimum Discards to Balance Inventory — CaffeCode