略譯

原題目連結

有 n 個包包，每個包包給你一個 <= 100萬 的整數，代表它的大小
小的包包可以裝進大的，但一樣大的不能互裝
一個包包只能塞入一個包包，但裝在包包裡的包包不計
比如說 1 塞在 2， 2 塞在 5 這樣 OK
1 和 2 一起塞在 5 這樣不 OK
求最少可以塞成剩幾個包包，並輸出一組解
若有多組解，則選塞最多層的包包最小的那一組
如果還是平手，則任一組均可

題解

從題意來看，不同大小的包包一定可以互裝，
並且被裝起來的小包包不影響裝它的大包包，
可知若大小完全不同，則一定可以全部塞進最大的包包。

從上推得，若需要多於一個包包，
那麼一定是因為有包包大小相同。

以 sample 的 1 1 2 2 2 3 為例，
我們可以把相同的排在一起，得到如下：

1 1
2 2 2
3

每一條直行都互不相同，都可以裝成一個包包；
由此可知，

最多有幾個相同大小的包包 = 最少需要裝成多少包包

又，題目要求有多組解時，要讓裝最多包包的那個盡量小；
換句話說就是裝得越平均越好。

怎樣最平均呢？一人一個，最公平嘛。

我們已知答案為 m，
則最佳情形為將 n 個包包，平均分成 m 排，如下：

第一排  第二排  第三排
----------------------
 a[0]    a[1]  
  1       1  
----------------------
                 a[2]
                  2  
----------------------
 a[3]    a[4]
  2       2  
----------------------
                 a[5]
                  3  
----------------------

將排序好的 n 個包包，依序分給 m 排，
分完 m 個後，再從第 1 排繼續分，分完即為所求；

由於同樣大小的東西最多不超過 m 個，
可證此分法絕不會有任一排出現相同大小的包包，
最後每排必能裝成一個包包。

實作提示

• 相同大小的東西，排序後會被放在一起
• 第 i 排為 a[m0+i], a[m1+i], a[m*2+i], …
  • for (i=0; i<m; i++)
    • for (j=i; j<n; j+=m)
      • …