BuildingTowersEasy
SRM 647 · 2014-12-30 · by lg5293
Problem Statement
The citizens of Byteland want to build N new buildings.
The new buildings will all stand in a line and they will be labeled 1 through N, in order.
The city regulations impose some restrictions on the heights of the new buildings.
You are given the parameters used in these restrictions: two
- The height of each building must be a nonnegative integer.
- The height of building 1 must be 0.
- The absolute value of the difference between any two adjacent buildings must be at most 1.
- For each valid i, the height of building x[i] must be t[i] or less.
Given these restrictions, the citizens of Byteland want to build a building that will be as tall as possible. Return the largest possible height some of the N buildings may have.
Constraints
- N will be between 1 and 100,000, inclusive.
- x will contain between 0 and min(N,50) elements, inclusive.
- t will have exactly the same number of elements as x.
- Each element of x will be between 1 and N, inclusive.
- x[i] < x[i+1] for all valid i.
- Each element of t will be between 0 and 100,000, inclusive.
10
{3,8}
{1,1}
Returns: 3
In this case we are going to build 10 buildings. We have two constraints: the height of building 3 can be at most 1, and the height of building 8 can also be at most 1. The tallest possible new building in this city can have height 3. One optimal skyline looks as follows: {0,1,1,2,3,3,2,1,1,0}.
100000
{}
{}
Returns: 99999
There are no additional constraints so, for each valid i, the height of building i can be (i-1).
2718
{1,30,400,1300,2500}
{100000,100000,100000,100000,100000}
Returns: 2717
20
{4,7,13,15,18}
{3,8,1,17,16}
Returns: 8
447
{32,35,55,60,61,88,91,97,128,151,181,186,192,196,198,237,259,268,291,314,341,367,389,390,391,428,435}
{81,221,172,641,25,953,330,141,123,440,692,394,200,649,78,726,50,810,501,4,216,407,2,172,0,29,14}
Returns: 120
Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BuildingTowersEasy with a public method int maxHeight(int N, vector<int> x, vector<int> t) · 59 test cases · 2 s / 256 MB per case