SkiResortsEasy
SRM 573 · 2012-12-13 · by rng_58
SRM 573 · 2012-12-13 · by rng_58 · Greedy
Problem Statement
Problem Statement
Fox Ciel is the owner of a ski resort. The ski resort has N places numbered 0 through N-1. You are given a int[] altitude. For each i, the i-th element of altitude is the altitude of the place i.
The skiers would like to follow the path (place 0) -> (place 1) -> ... -> (place N-1). The trip will only be possible if the altitudes of the places are non-increasing. In order to make the trip possible, Ciel now needs to decrease the altitudes of some places. In other words, Ciel wants to decrease some of the altitudes so that altitude[0] >= altitude[1] >= ... >= altitude[N-1] holds. It costs 1 unit of money to decrease the altitude of one place by 1 unit of height.
Return the minimal cost required for the change.
The skiers would like to follow the path (place 0) -> (place 1) -> ... -> (place N-1). The trip will only be possible if the altitudes of the places are non-increasing. In order to make the trip possible, Ciel now needs to decrease the altitudes of some places. In other words, Ciel wants to decrease some of the altitudes so that altitude[0] >= altitude[1] >= ... >= altitude[N-1] holds. It costs 1 unit of money to decrease the altitude of one place by 1 unit of height.
Return the minimal cost required for the change.
Constraints
- altitude will contain between 2 and 50 elements, inclusive.
- Each element of altitude will be between 0 and 1,000, inclusive.
Examples
0)
{30, 20, 20, 10}
Returns: 0
The altitudes are already non-increasing, so Ciel doesn't need to change anything.
1)
{5, 7, 3}
Returns: 2
Ciel should change the altitude of place 1 (0-based index) from 7 to 5. This changes the sequence of altitudes to {5, 5, 3}. The cost of the change is 7 - 5 = 2 units of money.
2)
{6, 8, 5, 4, 7, 4, 2, 3, 1}
Returns: 6
Ciel should change the altitudes to {6, 6, 5, 4, 4, 4, 2, 2, 1}.
3)
{23, 507}
Returns: 484
4)
{249, 739, 471}
Returns: 712
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SkiResortsEasy with a public method int minCost(vector<int> altitude) · 43 test cases · 2 s / 256 MB per case