Baloni
레이팅 미적용의견: 0
\(1^{st}\) round, October \(17^{th}\), 2015
There are N balloons floating in the air in a large room, lined up from left to right. Young Perica likes
to play with arrows and practice his hunting abilities. He shoots an arrow from the left to the right side
of the room from an arbitrary height he chooses. The arrow moves from left to right, at a chosen
height H until it finds a balloon. The moment when an arrow touches a balloon, the balloon pops and
disappears and the arrow continues its way from left to right at a height decreased by 1. Therefore, if
the arrow was moving at height H, after popping the balloon it travels on height \(H-1\).
Our hero’s goal is to pop all the balloons using as little arrows as possible.
In test cases worth 40%, it will hold \(N \le 5\,000\).
The first line of input contains the integer N (\(1 \le N \le 1\,000\,000\)).
The second line of input contains an array of N integers Hi.
Each integer Hi (\(1 \le Hi \le 1\,000\,000\)) is the height at which the i^{th} balloon floats, respectively from left
to right.
The first and only line of output must contain the minimal number of times Pero needs to shoot an
arrow so that all balloons are popped.
5
4 5 2 1 42
output
5
output
3Clarification of the first example: Our hero shoots the arrow at height 5 - which destroys [5, 4, 3],
and shoots an arrow at height 2 - which destroys [2, 1].
평가 및 의견
Baloni
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Baloni