问题2813--新年派对(parties)

2813: 新年派对(parties)

时间限制: 1 Sec  内存限制: 128 MB
提交: 6  解决: 5
[提交] [状态] [讨论版] [命题人:]

题目描述

新的一年到了,是时候和你的朋友聚在一起,回顾过去一年里发生的暖心事了。
n个人住在一个可以用数轴表示的城市里,第i个人住在一个整数坐标xi的房子里。第i个人可以和坐标xi - 1, xi+1一起来家里庆祝新年,或者呆在xi,每个人只能移动一次。对于房子在1或n的人,他们可以来到坐标0或n+1的房子。
例如,初始位置为x=[1,2,4,4]。最后的位置可以是[1,3,3,4],[0,2,3,3],[2,2,5,5],[2,1,3,5]等等。被占用的房屋总数等于在最终房屋中不同位置的总数。
所有人可以随意选择三种操作之一,然后计算有人的房屋总数。有人的房屋可能达到的最小数量和最大数量各是多少?

输入

第一行包含一个整数n,即人的数量。
第二行包含n个整数x1,x2,…,xn,即房子的坐标。

输出

输出两个整数,最小和最大可能的数目。

样例输入 Copy

4
1 2 4 4

样例输出 Copy

2 4

提示

在样例中,人们可以转到[2,2,3,3],x1到x1+1,x2不动,x3到x3 - 1,x4到x4 - 1。[1,1,3,3],[2,2,3,3]或[2,2,4,4]也是获得最小数量的选择。
对于已占用的房屋的最大数量,人们可以转到[1,2,3,4]或[0,2,4,5]。
【数据规模和约定】
30%数据   1<=n<=20
60%数据   1<=n<=2000
100%数据  1<=n<=2*10^5  1<=xi<=n

来源/分类