BuildingReorganization
SRM 531 · 2011-11-22 · by rng_58
Problem Statement
There are N buildings in the capital. They are located in a row and numbered 0, 1, ..., N-1 from left to right. The height of building i is heights[i] floors. Each floor of each building has the shape of a unit cube.
The current state of the capital is miserable: there are just buildings and no infrastructure, so people are unhappy. Michael decided to deconstruct two buildings and to build a mall and an entertainment center in their locations. The buildings that Michael wants to deconstruct have numbers A and B.
Deconstruction of buildings is a non-trivial process. It is organized as a sequence of operations. Each operation consists of exactly 4 steps:
- Choose one of two deconstructed buildings (A or B). Let X be the chosen building.
- Lower the topmost floor in X to the ground in front of building X. Lowering the floor by a unit of distance costs 1 coin. I.e., if the building now has H floors, the total cost of lowering the topmost floor is H-1 coins. Note that once we lower the topmost floor, the new height of the building becomes H-1.
- Choose a building Y different from A and B. Move the floor from the ground in front of building X to the ground in front of building Y. This operation costs cost * |X - Y| coins.
- Lift the floor onto the top of building Y. Lifting the floor by a unit of distance has the same cost as lowering it. I.e., it costs H coins to lift the currently processed floor on the top of a building that currently has H floors. Note that once we are done, the new height of building Y will be H+1.
Return the minimum possible total cost of the whole process, in coins.
Constraints
- heights will contain exactly N elements, where N is between 3 and 50, inclusive.
- Each element of heights will be between 1 and 500,000,000, inclusive.
- A will be between 0 and N - 2, inclusive.
- B will be between A + 1 and N - 1, inclusive.
- cost will be between 1 and 10,000,000, inclusive.
{5, 5, 5}
0
2
10
Returns: 215
There is not much choice here. All floors must be placed onto the top of building 1. The order in which individual floors of buildings 0 and 2 are deconstructed does not matter.
{440730690,320662314,299883498}
0
2
1267
Returns: 653829511396618764
{324571,159897,167677,374535}
0
2
2
Returns: 247327644616
{494767902,34,494551341,494760285,70343387}
0
3
9993264
Returns: 532820915143893602
{201091792,50805105,194422998,135796080,26696634,33080111}
0
1
105
Returns: 44757380421437558
{5, 5, 5, 5}
0
3
10
Returns: 190
All floors of building 0 should be placed onto the top of building 1. All floors of building 3 should be placed onto the top of building 2.
{5, 50, 1, 50, 5}
0
4
10
Returns: 275
Buildings 1 and 3 are very tall, so it's expensive to extend them. All floors of buildings 0 and 4 should go onto the top of building 2, in any order.
{5, 50, 1, 50, 5}
0
4
1000
Returns: 10540
The same case as above, but horizontal movement is much more expensive. Now it's cheaper to extend buildings 1 and 3.
Submissions are judged against all 96 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BuildingReorganization with a public method long long theMin(vector<int> heights, int A, int B, int cost) · 96 test cases · 2 s / 256 MB per case