CodeForces 388A Fox and Box Accumulation

本文主要是介绍CodeForces 388A Fox and Box Accumulation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：http://codeforces.com/problemset/problem/388/A

Fox Ciel has n boxes in her room. They have the same size and weight, but they might have different strength. The i-th box can hold at most x_i boxes on its top (we'll call x_i the strength of the box).

Since all the boxes have the same size, Ciel cannot put more than one box directly on the top of some box. For example, imagine Ciel has three boxes: the first has strength 2, the second has strength 1 and the third has strength 1. She cannot put the second and the third box simultaneously directly on the top of the first one. But she can put the second box directly on the top of the first one, and then the third box directly on the top of the second one. We will call such a construction of boxes a pile.

$\text{[math]}$

Fox Ciel wants to construct piles from all the boxes. Each pile will contain some boxes from top to bottom, and there cannot be more than x_i boxes on the top of i-th box. What is the minimal number of piles she needs to construct?

Input

The first line contains an integer n (1 ≤ n ≤ 100). The next line contains n integers x₁, x₂, ..., x_n (0 ≤ x_i ≤ 100).

Output

Output a single integer — the minimal possible number of piles.

Sample test(s)

Input

3
0 0 10

Output

Input

5
0 1 2 3 4

Output

Input

4
0 0 0 0

Output

Input

9
0 1 0 2 0 1 1 2 10

Output

Note

In example 1, one optimal way is to build 2 piles: the first pile contains boxes 1 and 3 (from top to bottom), the second pile contains only box 2.

$\text{[math]}$

In example 2, we can build only 1 pile that contains boxes 1, 2, 3, 4, 5 (from top to bottom).

$\text{[math]}$

大意——给定n个箱子，它们具有相同的大小和重量，但是它们有不同的承受力。一个箱子的承受力是指它的上面最多能够放几个箱子。按箱子的承受力从小到大往下面放，即承受力大的放在下面，承受力小的放在上面，并且保证放在下面的箱子的承受力要大于它的上面的箱子数目，这就是一个堆。现在给你这n个箱子的承受力，问你至少需要几个堆才能够将箱子放完。

思路——明显的贪心。首先将箱子的承受力按照从小到大排序，接着便可以从这些箱子里面选择了。怎么选才是最优的呢？很明显，每次尽量多选择箱子即可。这样的话，我们可以先找出最小承受力的箱子放在最上面，接着找到能承受前面箱子的尽量小承受力的箱子，一直下去，直至找不到为止。计数加一，第二次将剩下的箱子用同样的方法处理，直至处理完所有箱子，最后得到的解一定是最优的。

复杂度分析——时间复杂度:O(n^2),空间复杂度:O(n)

附上AC代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
//#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const short maxn = 105;
short box[maxn];
short n;int main()
{ios::sync_with_stdio(false);while (~scanf("%hd", &n)){for (short i=0; i<n; i++)scanf("%hd", box+i);sort(box, box+n);int cnt=0, num, sum=n;while (sum){num = 0;for (short i=0; i<n; i++)if (box[i] >= num){box[i] = -1;num++;sum--;}cnt++;}printf("%d\n", cnt);}return 0;
}

这篇关于CodeForces 388A Fox and Box Accumulation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！