首页 > ACM题库 > HDU-杭电 > hdu 2796 Coin Piles待解决[解题报告]C++
2014
02-14

hdu 2796 Coin Piles待解决[解题报告]C++

Coin Piles

问题描述 :

We have some coins on the table. Each coin is characterized by its size. We want to arrange these coins into successive piles so that the following hold:

1. The size of the top coin in each pile is strictly greater than the size of all the other coins in the same pile.
2. The size of the top coin in each pile is strictly greater than the size of the top coin in the previous pile.
3. The number of coins in each pile is strictly greater than the number of coins in the previous pile.

You will be given the size of each coin. You are to calculate the maximal number of piles that we can organize according to the given rules. Each coin should be used in exactly one pile.

输入:

There are multiple cases (no more than 100).

There is two lines for each case. The first line is a number n (1 <= n <= 50), indicating the number of coins. A line with n integers follows, giving the sizes of the coins.

Note that the maximal of the sizes will be unique, so it’s always possible to form at least one pile.

输出:

There are multiple cases (no more than 100).

There is two lines for each case. The first line is a number n (1 <= n <= 50), indicating the number of coins. A line with n integers follows, giving the sizes of the coins.

Note that the maximal of the sizes will be unique, so it’s always possible to form at least one pile.

样例输入:

6
1 2 2 2 2 3
6
1 1 2 2 2 3
6
1 2 2 2 3 4

样例输出:

2
3
3


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。