Toggle navigation
PIPIOJ
F.A.Qs
Web Board
ProblemSet
Source/Category
Status
Ranklist
Contest
Recent
Login
Problem1023--巨人排队
1023: 巨人排队
Time Limit:
1 Sec
Memory Limit:
128 MB
Submit:
2843
Solved:
659
[
Submit
] [
Status
] [
Web Board
] [Creator:
]
Description
巨人国的小学生放假了,老师要给小朋友们排队了。可是这个老师有强迫症,一定要路队上的小朋友按照身高从高到矮排序(也就是排在前面的不能比后面的矮)。小朋友呢也很调皮,一旦老师给他排好队就不愿意动了。这个时候小朋友们一个一个的从教室里出来了,每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友排几条路队呢?
Input
对于每组数据,第一行一个数
n
,表示小朋友总数量
(1<=n<=100000)
第二行
n
个整数,表示小朋友身高,身高不超过
30000
Output
对于每组数据,输出一个整数,表示最少的路队数
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
HINT
最少要排两条路队,其中一种方案是
398-207-155-65
和
300-299-170-158
Source/Category
2017年中南大学研究生复试机试题