RYIP在线题库
首 页   >   习题练习   >   提交
Problem2213--动物园(zoo)

2213: 动物园(zoo)

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

【 Description 】

某动物园里有n个场馆和m种动物(�m≤n)。
n个场馆的编号分别用 1,2,3, . . , n表示;m种动物的编号分别用 1,2,3, . . ,m表示。每一个场馆中只饲养了一只动物,不同的场馆可能饲养着相同种类的动物。
这个动物园的门票比较特殊,游客在购买门票时必须说明要参观的场馆的起止编号a和 b(起止编号会打印到游客购买的门票上),代表游客只能参观动物园的第 � 个场馆至第 � 个场馆(包含a,b�)里的动物,其他的场馆不能去。门票按一个场馆十元收费。
如果你购买的门票的起止场馆编号是 3 到 8,那么你需要花 60 元钱购买门票,只能观看3,4,5,6,7,8 号场馆的动物。
小明希望看到动物园内所有种类的动物,同时小明是个非常节约的孩子,他希望花最少的钱买门票。 请你帮小明计算:他最少需要花费多少钱买门票才能看到所有种类的动物(同一种动物他可能不止看一个)。注意:小明只能买一张门票。 

【 Input 】

第一行两个整数n�, m,分别表示动物园内的场馆数量及动物种类数量。
第二行是 �x1, x2, . . . ,xn,其中xi表示第 i个场馆中的动物种类编号。

【 Output 】

一行一个整数 �p,表示小明的门票费用。 

【 Sample Input 】

12 5
2 5 3 1 3 2 4 1 1 5 4 3

【 Sample Output 】

60

【HINT】

样例 1 说明:花费最少的其中一种购票方案选择是 � a= 2, � b= 7 ,表示购买场馆 2,3,4,5,6,7
的门票,分别看到的动物是 5,3,1,3,2,4 ,其中动物 3 小明看了两个。 
数据范围
• 对于 30% 的数据,有 � n≤ 200 , �m ≤ 20。
• 对于 60% 的数据,有 n� ≤ 1000 , m≤ 1000。
• 对于 100% 的数据,有 1 ≤n � ≤ 10^6,1 ≤xi�� ≤ m� ≤ 2 × 10^3。

【 Source/Category 】

TX